3203: [Sdoi 2013] 출제자 보호 + 3점

3258 단어 My Code

IOI 할아버지 문제풀이 3점.

#include
#include
#define N 100105
using namespace std;
int n,top,stack[N];
double d;
double sum[N],x[N];
struct node {double x,y;} a[N];
double cross(node a,node b,node c)
{
    return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
double slop(node a,node b)
{
    return (a.y-b.y)/(a.x-b.x);
}
double find(node t)
{
    int l=1,r=top,lmid,rmid;
    while (r-l>=3)
    {
        lmid=l+(r-l)/3;
        rmid=r-(r-l)/3;
        double K1=slop(a[stack[lmid]],t),K2=slop(a[stack[rmid]],t);
        if (K1else r=rmid;
    }
    double ans=0.0;
    for (int i=l;i<=r;i++) ans=max(ans,slop(a[stack[i]],t));
    return ans;
}
int main()
{
    scanf("%d%lf",&n,&d);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&sum[i],&x[i]);
        sum[i]+=sum[i-1]; 
        a[i]=(node){i*d,sum[i-1]};
    }
    double ans=0;
    for (int i=1;i<=n;i++)
    {
        while (top>1&&cross(a[i],a[stack[top]],a[stack[top-1]])>=0) top--;
        stack[++top]=i;
        node q=(node){x[i]+i*d,sum[i]};
        ans+=find(q);
    }
    printf("%.0lf
",ans);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Ubuntu 에서 Oh My Zsh 의 가장 좋 은 실천 '설치 및 설정'

예 를 들 어 테마 설정, 플러그 인 체제, 내 장 된 편리 한 조작 등 은 우리 에 게 새로운 명령 행 사용 체험 을 줄 수 있 습 니 다.다음은 Oh My Zsh 의 설치 및 배치 방법 을 정리 하고 가장 좋 은...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다