제출 #221880

#제출 시각아이디문제언어결과실행 시간메모리
221880MKopchevBuilding Bridges (CEOI17_building)C++14
30 / 100
138 ms53752 KiB
#include<bits/stdc++.h> using namespace std; const int nmax=1e5+42; const int MX=4*2*nmax; int n; long long h[nmax],w[nmax],pref[nmax]; long long dp[nmax]; set<long long> coeffs; long long x_mult[nmax],pointer=0; pair<long long,long long> tree[MX]; long long eval(pair<long long,long long> line,long long x) { return x*line.first+line.second; } long long query(int node,int l,int r,int x) { if(l==r)return eval(tree[node],x); long long ret=eval(tree[node],x); int av=(l+r)/2; if(x<=x_mult[av])return min(query(node*2,l,av,x),ret); return min(query(node*2+1,av+1,r,x),ret); } void add_line(int node,int l,int r,pair<long long,long long> current_line) { //cout<<"add line "<<node<<" "<<l<<" "<<r<<" "<<current_line.first<<" "<<current_line.second<<endl; if(eval(tree[node],x_mult[l])<=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[r])<=eval(current_line,x_mult[r]))return;//tree[node] is better than current_line if(eval(tree[node],x_mult[l])>=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[r])>=eval(current_line,x_mult[r]))//current_line is better than tree[node] { tree[node]=current_line; return; } //now l!=r int av=(l+r)/2; //tree[node] is better in [x[l],x[av]] if(eval(tree[node],x_mult[l])<=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[av])<=eval(current_line,x_mult[av])){add_line(node*2+1,av+1,r,current_line);return;} //current is better in [x[l],x[av]] if(eval(tree[node],x_mult[l])>=eval(current_line,x_mult[l])&&eval(tree[node],x_mult[av])>=eval(current_line,x_mult[av])){add_line(node*2+1,av+1,r,tree[node]);tree[node]=current_line;return;} //tree[node] is better in [x[av+1],x[r]] if(eval(tree[node],x_mult[av+1])<=eval(current_line,x_mult[av+1])&&eval(tree[node],x_mult[r])<=eval(current_line,x_mult[r])){add_line(node*2,l,av,current_line);return;} //current is better in [x[av+1],x[r]] if(eval(tree[node],x_mult[av+1])>=eval(current_line,x_mult[av+1])&&eval(tree[node],x_mult[r])>=eval(current_line,x_mult[r])){add_line(node*2,l,av,tree[node]);tree[node]=current_line;return;} assert(0==1);//should not happen } int main() { scanf("%i",&n); for(int i=1;i<=n;i++)scanf("%lld",&h[i]); for(int i=1;i<=n;i++){coeffs.insert(-2*h[i]);coeffs.insert(h[i]);} for(auto k:coeffs) { pointer++; x_mult[pointer]=k; } for(int i=0;i<MX;i++)tree[i]={0,1e18}; for(int i=1;i<=n;i++)scanf("%lld",&w[i]); for(int i=1;i<=n;i++)pref[i]=pref[i-1]+w[i]; /* cout<<"pointer= "<<pointer<<endl; for(int i=1;i<=pointer;i++)cout<<x_mult[i]<<" ";cout<<endl; */ for(int j=1;j<=n;j++) { dp[j]=h[j]*h[j]+pref[j-1]+query(1,1,pointer,h[j]); if(j==1)dp[j]=0; add_line(1,1,pointer,{-2*h[j],h[j]*h[j]-pref[j]+dp[j]}); //cout<<j<<" -> "<<dp[j]<<endl; } printf("%lld\n",dp[n]); return 0; }

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

building.cpp: In function 'int main()':
building.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
building.cpp:69:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
                          ~~~~~^~~~~~~~~~~~~~
building.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
                          ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...