제출 #941337

#제출 시각아이디문제언어결과실행 시간메모리
9413378pete8Building Bridges (CEOI17_building)C++17
0 / 100
43 ms9104 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<limits.h> #include <cassert> #include <cstdint> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") using namespace std; #define int long long #define double long double const int mod=1e9+7,mxn=1e6+5,lg=30,inf=1e18,minf=-1e18; int mode=1; struct line{ int m,c; mutable int p; int get(int x) const{return (m*x)+c;} bool operator<(line a)const{ if(mode)return m>a.m; else return p<a.p; } }; struct cht{ multiset<line>v; int div(int a,int b){return (a/b)-(!(a%b==0||(a*b)>=0));} int intersect(multiset<line>::iterator a,multiset<line>::iterator b){return div((a->c-b->c),(b->m-a->m));} void cal(multiset<line>::iterator a){a->p=((a==v.end())?inf:intersect(a,next(a)));} bool bad(multiset<line>::iterator a,multiset<line>::iterator b){ if(b==v.end())return a->p=inf,0; if(a->m==b->m)return a->c<b->c; a->p=intersect(a,b); return a->p>b->p; } void add(line a){ auto it=v.insert(a); while(bad(it,next(it)))v.erase(next(it)); if(it!=v.begin()&&bad(prev(it),it))bad(prev(it),it=v.erase(it)); if(it!=v.begin())it=prev(it); while(it!=v.begin()&&bad(prev(it),it)){ bad(prev(it),it=v.erase(it)); it=prev(it); } } int qry(int x){ if(v.empty())return inf; mode=0; auto it=v.lb((line){0,0,x})->get(x); mode=1; return it; } }t; int v1[mxn+10],v2[mxn+10],dp[mxn+10]; int32_t main(){ fastio int n;cin>>n; for(int i=1;i<=n;i++)cin>>v1[i]; for(int i=1;i<=n;i++)cin>>v2[i],v2[i]+=v2[i-1]; t.add((line){-2*v1[1],-v2[1]+(v1[1]*v1[1]),0}); for(int i=2;i<=n;i++){ dp[i]=t.qry(v1[i])+(v1[i]*v1[i])+v2[i-1]; t.add((line){-2*v1[i],dp[i]-v2[i]+(v1[i]*v1[i]),0}); } cout<<dp[n]; }

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

building.cpp: In member function 'void cht::add(line)':
building.cpp:62:53: warning: operation on 'it' may be undefined [-Wsequence-point]
   62 |   if(it!=v.begin()&&bad(prev(it),it))bad(prev(it),it=v.erase(it));
      |                                                   ~~^~~~~~~~~~~~
building.cpp:65:19: warning: operation on 'it' may be undefined [-Wsequence-point]
   65 |    bad(prev(it),it=v.erase(it));
      |                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...