제출 #129972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129972		TadijaSebez	Building Bridges (CEOI17_building)	C++11	100 / 100	90 ms	35672 KiB

building

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
const int N=1000050;
const int M=2*N;
const ll inf=9e18;
struct Line
{
    ll k,n;
    Line(ll a=0, ll b=0){ k=a,n=b;}
    ll Get(ll x){ return x*k+n;}
} line[M];
int ls[M],rs[M],tsz,root;
void Swap(Line &a, Line &b){ Line tmp=a;a=b;b=tmp;}
void Set(int &c, int ss, int se, Line k)
{
    if(!c){ c=++tsz;line[c]=k;return;}
    ll A=line[c].Get(ss),B=k.Get(ss),C=line[c].Get(se),D=k.Get(se);
    if(A>=B && C>=D) return;
    if(A<=B && C<=D){ line[c]=k;return;}
    int mid=ss+se>>1;
    if(A<B) Swap(line[c],k);
    if(line[c].Get(mid)>=k.Get(mid)) Set(rs[c],mid+1,se,k);
    else Swap(line[c],k),Set(ls[c],ss,mid,k);
}
ll Get(int c, int ss, int se, int qi)
{
    if(!c) return -inf;
    if(ss==se) return line[c].Get(qi);
    int mid=ss+se>>1;
    if(qi<=mid) return max(line[c].Get(qi),Get(ls[c],ss,mid,qi));
    else return max(line[c].Get(qi),Get(rs[c],mid+1,se,qi));
}
int h[N],w[N];
ll sum[N],dp[N];
int main()
{
    int n,i;
    scanf("%i",&n);
    for(i=1;i<=n;i++) scanf("%i",&h[i]);
    for(i=1;i<=n;i++) scanf("%i",&w[i]),sum[i]=sum[i-1]+w[i];
    dp[1]=0;
    Set(root,0,N-1,Line((ll)2*h[1],(ll)-h[1]*h[1]+sum[1]+dp[1]));
    for(i=2;i<=n;i++)
    {
        dp[i]=(ll)-h[i]*h[i]-sum[i-1]+Get(root,0,N-1,h[i]);
        Set(root,0,N-1,Line((ll)2*h[i],(ll)-h[i]*h[i]+sum[i]+dp[i]));
    }
    //for(i=1;i<=n;i++) printf("%lld ",dp[i]);printf("\n");
    printf("%lld\n",-dp[n]);
    return 0;
}

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

building.cpp: In function 'void Set(int&, int, int, Line)':
building.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
building.cpp: In function 'long long int Get(int, int, int, int)':
building.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=ss+se>>1;
             ~~^~~
building.cpp: In function 'int main()':
building.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
building.cpp:45:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%i",&h[i]);
                       ~~~~~^~~~~~~~~~~~
building.cpp:46:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++) scanf("%i",&w[i]),sum[i]=sum[i-1]+w[i];
                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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