제출 #881802

#제출 시각아이디문제언어결과실행 시간메모리
881802HA_Blue2809Building Bridges (CEOI17_building)C++14
100 / 100
52 ms73348 KiB
// G&B 7&& #&&&# J&&&&&&&J G&&&& &&& B&5 B&P J&# &&&&&& #&&&&&&&5 // // B@# ?@@ #@&#@& Y@@57Y@@J B@@ @@7 #@P #@G Y@@ @@ J@@57J@@P // // B@#7#&@@ &@& 5@& J@@ @@J B@@ B# @@7 #@P #@G Y@@ @@###Y 7@@ &@P // // B@# 5@@ &@& P@& Y@@ @@J #@@ @ @@? &@P #@G 5@@ @@ ?@@ &@P // // B@# 7@@ @@@@B P@& Y@@ @@J #@@@&&@@@ @@@&&@@G #@@&&@@@ @@&#&& 7@@ &@G // // 7@# P@P &@? P@G &@? // // ?# PP &7 5G &7 // // 7 7 7 7 7 // #include <bits/stdc++.h> #define file "XAYCAU" #define FastIO ios_base::sync_with_stdio(false),cin.tie(NULL) #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout) #define endl " \n" #define _ <<' '<< #define el <<'\n' #define f first #define s second #define mp make_pair #define mp3(a,b,c) mp(a,mp(b,c)) #define pb push_back #define eb emplace_back #define si(a) ((int)a.size()) #define all(a) a.begin(),a.end() #define mset(a,i) memset(a,i,sizeof a) #define maxi(a,b) a=max(a,b) #define mini(a,b) a=min(a,b) #define bit(x,i) (((x)&P[i])>0) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef pair<ll,ll> pii; typedef pair<int,pii> piii; typedef pair<pii,pii> p4; const int maxn=1e6+69; const ll mod=1e9+7; struct line{ ll a,b; ll operator()(ll x){ return a*x+b; } }T[maxn*4]; int n; ll H[maxn],W[maxn],F[maxn],sum=0; void add(line a,int it=1,int l=0,int r=1e6){ if (r-l==1){ if (a(l)<T[it](l)) T[it]=a; return; } int mid=(l+r)>>1,t=it<<1,p=it<<1|1; if (T[it].a<a.a) swap(T[it],a); if (T[it](mid)>a(mid)){ swap(T[it],a); add(a,t,l,mid); } else add(a,p,mid,r); } ll get(int x,int it=1,int l=0,int r=1e6){ if (r-l==1) return T[it](x); int mid=(l+r)>>1,t=it<<1,p=it<<1|1; if (x<mid) return min(T[it](x),get(x,t,l,mid)); return min(T[it](x),get(x,p,mid,r)); } int main() { FastIO; OpenFile; cin>>n; for(int i=1;i<=n;i++) cin>>H[i]; for(int i=1;i<=n;i++){ cin>>W[i]; sum+=W[i]; } for(int i=0;i<maxn*4;i++) T[i]={(ll)1e9,(ll)1e18}; F[1]=-W[1]; for(int i=2;i<=n;i++){ add({-2LL*H[i-1],H[i-1]*H[i-1]+F[i-1]}); F[i]=get(H[i])+H[i]*H[i]-W[i]; } cout<<F[n]+sum; return 0; } // ▒███████▓▒░ // ███▓░░░░░░░████▓ // ░██░░░░░░░░███▓ ░▒ // ██████████████████████████ ██░░░░░░░██▓▓█████▒ // ███████░░░░░░░███░░░░░░░░░░░░░░░███▓ ▓███░░░░░████▒░░░▒████ // █████████████░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░████████▓▓██░░░███░░░░░░░░░░██░ // ▒██░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░░░░░░░░▓██████▓▓▓▓██░██▓░░░░░░░░░░░░▒█ // ░███░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██▓▓▓▓██▓███████▓████████░░░░░░█▓ // ███▓░░░░░░██░░░░░░░█░░░░░░░░░░░░░█▓░░░░░▒█▓▓▓▓▓▓██▓▓███▓▓▓█▓ ███░░░██▒ // █▓░░░░██░░░░░░░░█▓░░░░░░░░░░░░░░█▓░░░░░░███▓▓▓██▓▓▓▓▓▓▓██ ░█▓░███ // ▒█▒░░░██░░░░░░░░░██░░░░░░░░░░░░░░▓██▓░░░░░░▒█████████▓▓▓███ ▓████░ // ░█▒░░░██░░░░░░░░░░██░░░░░░░░░░░░░░████░░░░░░░░░░▒█████████░▓█ ███ // ██░░░██░░░░░░░░░░▒█▒░░░░░░░░░░░░░██░▓██░░░░░░░░░░░░░░░░█▓░░░█▓ // ▒█▒░░░█▒░░░░░░░░░░▒█▒░░░░░░░░░░░░▓██░░▒██░░░░░░░░░░░░░░░░░░░░▒█░ // ██░░░███░░░░░░░░░░██▒░░░░░░░░░░░▒██░░░░░██░░░░░░░░░░░░░░░░░░░░██ // ██░░░▒███░░░░░░░░████▓░░░░░░█░░░▒██▒░░░░░░██░░░░░░░░█▒▒██░░░░░░██▓ // ██░░░░████░░░░░░██▓ ██░░░░░██░░▒██░█▒░░░░░░██░░░░░░░██▒▒██░░░░░░██░ // ██░░░░██░▒██░░░░█▓ ▒█▒░░░███░▓█▒ ▓█░░░░░░▒█▒░░░░░░▒██░░██░░░░░░██░ // ░█▒░░░░██░░░███▒▒█▒ ▓█░░░█████░ ▓██░░░░░██░░░░░░░██░░░██░░░░░░████▒ ▓ // ██░░░░░██▒░░▓█░████ ▓█▓▒█░█▓ ░██▓░░░░██░░░░░░▓█▓░░▒██▓░░░░░░░▓██████ // ░█▒░░░░░██▓░░██ ░███ ░ ▒███░░██░░░░░░▒██░░░████▓░░░░░░▒██▓ // ███████████░▒█▒ ██ ▒████▒░░░░░▒██░░░░██▒▓██████▓ // ██░██░ ██░░░░░███░░░░▒██░░██ // ▒█▓▒█░ ▓█░░░░▒██▓░░░░░██▓░░█▒ // ██░█▓ ██ ▓▓░░░▒███▒░░░░░▒██░░█▓ // ██░▒█ ██████████████ █▒░░█████░░░░░░░██░░█▒ // ██░░██ █▓▓▓▓▓▓▓▓▓▓▓██ ░█░▓██▓██▓░░░░░░░██░░█▒ // ██░████░ ██▓▓▓▓▓▓▓▓██ █████ ░██░░░░░░░███░░█░ // ██████▓██ █▓▓▓▓▓▓██ ▓█▓░ ▒█▓░░░░░░░░██░░░█░ // ███ ██░░██░ █████ ░██░░░░░░░░░██▒░░░█░ // ██░░░░███░ ░░██▓░░░░░░░░░░██▒░░░░█░ // ██░░▓░░░███▓░ ▒███▓░░░░░░░░░░░███░░░░░░█▒ // ██████▓░░░▒████▓░ ░█▓░░░░░░░░░░██▓ ██▓░░░░▒█ // ▓██ ░████████████████▓▓░░░░░░░░░░▒██████▓▒▒▒▓██▓ ▒███▒░░██ // ▒ ▒█████░ ▓█▓▓▓▓███▓████████████░░░▒█████░░▒█▒ ▒████ // ▒▓████▓ ▒█▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓█ ▓███████ // ▓███▓▓▓▓ ░█▓▓▓▓███▓▓▓▓▓▓▓▓▓▓██ ▓▓▓▓▓████▓ // ░████░███▓▓▓█▓ ░████▓██▓██████████▓▒ ░▓▓▓▓████▓██▓ // ░███ ░█████ ██▓▓██▓▓▒███▓███▒ ███░▓▓▓▓███░▒████▒ // ▒██▒░██ ██████ ███ ▓▓ ░█████ ░████████░ ░██░▓▓█▒ ░██ //███████████████▒░░░░▒█░ ██░░░█░ ▒▓ ▓█░░░▒█░ ██░░▒▓████▓▓░ ████ // █▒░░░░░░░██▒░░░░░░░▒█░ ▒█▒░████▓▓▓▓█████████▒ ▓████▓██░ ██▓░░▓▓░░▒▓▓███░ ███░▒██ // ░██░░▒██▓░░░░░░░░░░▓██ ░██░ ░ ▒█▓▓▓▓▓▓▓▓▓▓██████████░ █▓ ██▒░░░▒▓░▒▓▓░░█████████████▓░░░░░██ // ██▓░░░░░░░░░░▒██▓ █▓ ░█░ ███████████▓▓▓▓▓███████████████▒██████░░░▓▓▓▓░░░░░░░░███▒░░░░░░░░░██ // ▓█░░░░░░░░▓██▒ ░█▓███████▓▓▓▓██████████████▓▓▓▓▓▓▓▓▓▓████▓ ▓██▓▓▓░░░░░░░░░░░░░▓██▒░░░███ // █▒░░░░░░▓██ ████▓▓▓▓▓████ ██▓▓▓▓▓▓▓█░████▓▓▓▓▓▓▓████▒ ▓▓▓▓███▒░░░░░░░░░░░▒█████▒ // █▓░░░░░██ ░███▓▓▓████▓ ██▓▓▓▓▓▓▓▓█▒ ░█████████▒ ██ ▓▓ ░▓ ███▒░░░░░░░░░███ // ██▒░░░██ █▓▓██████ ░██▓▓▓▓▓▓▓▓▓█▒ ░███████████ ░▓▓▓▓▓▓▓▒ ▒██▒░░░░░░░██ // ███░░█▓ ██▓█████████████████████████████▒ █████████ ██░░░░░░██ // ▓█████ ████████▒ ░████████ █▒░░░░██ // ░███████ ███████▒ █▒░░▓█ // ██████░ ██████ ██░▓█▒ // ▒███ ███ ████░ // ░████

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

building.cpp: In function 'int main()':
building.cpp:12:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:66:10: note: in expansion of macro 'OpenFile'
   66 |  FastIO; OpenFile;
      |          ^~~~~~~~
building.cpp:12:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:66:10: note: in expansion of macro 'OpenFile'
   66 |  FastIO; OpenFile;
      |          ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...