Submission #981583

#TimeUsernameProblemLanguageResultExecution timeMemory
981583vjudge1Aliens (IOI16_aliens)C++17
100 / 100
115 ms6232 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pb push_back #define sz(x) (int)(x.size()) #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define vi vector<int> #define vp vector<pii> #define vvi vector<vi> #define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) #define __lg(x) 63-__builtin_clzll(x) #define pow2(x) (1LL<<x) const int mxn=1e5+5; pair<int,int>p[mxn]; int n,m; pair<long long,int> calc(tuple<int,long long,int>f,int x){ return {1LL*get<0>(f)*x+get<1>(f),get<2>(f)+1}; } bool ck(tuple<int,long long,int>l1,tuple<int,long long,int>l2,tuple<int,long long,int>l){ auto [m1,b1,c1]=l1; auto [m2,b2,c2]=l2; auto [m,b,c]=l; //l1*l2<l2*l //(b1-b2)/(m2-m1)>(b1-b)/(m-m1) //(b1-b2)*(m-m1)>=(b1-b)*(m2-m1) return make_pair(1LL*(b1-b)*(m2-m1),c)<=make_pair(1LL*(b1-b2)*(m-m1),c2); } pair<long long,int> solve(long long cost){ deque<tuple<int,long long,int>>st; st.pb({-2*p[1].F,1LL*p[1].F*p[1].F,0}); pair<long long,int>dp; for(int i=1;i<=n;i++){ while(sz(st)>1 and calc(st[0],p[i].S)>=calc(st[1],p[i].S)){ st.pop_front(); } dp=calc(st.front(),p[i].S); dp.F+=1LL*p[i].S*p[i].S+cost; if(i==n) break; int d=max(0,p[i].S-p[i+1].F); tuple<int,long long,int>l={-2*p[i+1].F,dp.F+1LL*p[i+1].F*p[i+1].F-1LL*d*d,dp.S}; while(sz(st)>1 and ck(st.end()[-2],st.back(),l)){ st.pop_back(); } st.pb(l); } return dp; } bool cmp(pair<int,int>a,pair<int,int>b){ return (a.F==b.F?a.S>b.S:a.F<b.F); } long long take_photos(int N,int M,int k,vector<int>R,vector<int>c){ n=N; m=M; vector<pii>v; for(int i=0;i<n;i++){ if(c[i]<R[i])swap(R[i],c[i]); p[i+1]={R[i],c[i]+1}; } sort(p+1,p+n+1,cmp); int sz=0; for(int i=1;i<=n;i++){ if(sz==0 or p[i].S>p[sz].S)p[++sz]=p[i]; } n=sz; long long l=0,r=1e15; while(l<r){ long long mm=l+r>>1; pair<long long,int> x=solve(mm); if(x.S>k){ l=mm+1; } else{ r=mm; } } return solve(l).F-1LL*l*k; } #ifdef local signed main(){ freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin); int n,m,k; cin>>n>>k >> m; vector<int> r(n),c(n); for(int i=0;i<n;i++){ cin>>r[i]>>c[i]; } cout<<take_photos(n,m,k,r,c)<<'\n'; } #endif

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:72:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         long long mm=l+r>>1;
      |                      ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...