제출 #169589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169589		Ruxandra985	Building Bridges (CEOI17_building)	C++14	100 / 100	115 ms	36728 KiB

building

#include <bits/stdc++.h>
#define DIMN 100010
#define DIMH 1000010
#define INF 1000000000000000000

using namespace std;
struct idk{
    long long x,y;
} aint[4*DIMH];
long long h[DIMN] , spw[DIMN] , dp[DIMN],dp2[DIMN];
void update (long long nod,long long st,long long dr,long long x,long long y){
    if (st == dr){
        if (aint[nod].x * st + aint[nod].y > x * st + y){
            aint[nod].x = x;
            aint[nod].y = y;
        }
        return;
    }
    long long mid = (st+dr)/2,st1=0,st2=0;
    if (aint[nod].x * mid + aint[nod].y > x * mid + y)
        st1 = 1;
    if (aint[nod].x * dr + aint[nod].y > x * dr + y)
        st2 = 1;

    if (!st1 && !st2){
        update (2*nod,st,mid,x,y);
    }
    else if (!st1 && st2) {
        update (2*nod+1,mid+1,dr,x,y);
    }
    else if (st1 && !st2){
        swap(x,aint[nod].x);
        swap(y,aint[nod].y);
        update (2*nod+1,mid+1,dr,x,y);
    }
    else if (st1 && st2){
        swap(x,aint[nod].x);
        swap(y,aint[nod].y);
        update (2*nod,st,mid,x,y);
    }

}
long long query (long long nod,long long st,long long dr,long long x){
    if (st==dr){
        return aint[nod].x * x + aint[nod].y;
    }
    long long mid = (st+dr)/2;
    long long sol = INF;
    if (x<=mid)
        sol = query(2*nod,st,mid,x);
    else sol = query(2*nod+1,mid+1,dr,x);
    return min(sol , aint[nod].x * x + aint[nod].y);
}
void build (long long nod,long long st,long long dr){
    int mid = (st + dr)/2;

    aint[nod].x = aint[nod].y = 1000000000000;

    if (st == dr)
        return;

    build (2*nod,st,mid);
    build (2*nod+1,mid+1,dr);

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int i , n;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld",&h[i]);
    }
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld",&spw[i]);
        spw[i] += spw[i-1];
    }
    build (1,1,DIMH-10);
    for (i=1;i<=n;i++){
        if (i >= 2)
            dp[i] = h[i] * h[i] + spw[i-1] + query (1,1,DIMH-10,h[i]);
        update (1,1,DIMH-10, -2 * h[i] , h[i] * h[i] - spw[i] + dp[i]);
    }
    fprintf (fout,"%lld\n",dp[n]);
    /*dp2[1] = 0;
    for (i=2;i<=n;i++){
        dp2[i] = INF;
        for (int j=i-1;j;j--){
            dp2[i] = min(dp2[i] , dp2[j] + (h[i] - h[j]) * (h[i] - h[j]) + spw[i-1] - spw[j]);
        }
        if (dp2[i] != dp[i])
            fprintf (fout,"%d\n",i);
    }
    fprintf (fout,"\n%lld",dp2[n]);*/
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In function 'int main()':
building.cpp:71:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
building.cpp:73:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&h[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
building.cpp:76:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&spw[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40