제출 #792011

#제출 시각아이디문제언어결과실행 시간메모리
792011I_Love_EliskaM_Aliens (IOI16_aliens)C++14
25 / 100
1445 ms1048580 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define all(x) x.begin(), x.end() #define pi pair<int,int> #define f first #define s second using ll = long long; #define int ll const int inf=1e18; int sq(int x) { return x*x; } struct line { int a,b; int f(int x) { return a*x+b; } line() { a=0, b=inf; } line(int x, int y) { a=x, b=y; } }; const int sz=1<<20; struct sgt { sgt *L, *R; line ln; sgt() { L=R=NULL; ln=line(); } sgt(line n) { L=R=NULL; ln=n; } void add(int l, int r, line n) { if (n.f(l)<=ln.f(l) && n.f(r)<=ln.f(r)) { ln=n; return; } if (n.f(l)>=ln.f(l) && n.f(r)>=ln.f(r)) { return; } if (r-l==1) return; int m=(l+r)>>1; if (!L) L=new sgt(ln); if (!R) R=new sgt(ln); L->add(l,m,n); R->add(m,r,n); } void add(line n) { add(0,sz,n); } int query(int l, int r, int x) { if (r<=x || l>x) return inf; int m=(l+r)>>1; int f=ln.f(x); int s=L?L->query(l,m,x):inf; int t=R?R->query(m,r,x):inf; return min({f,s,t}); } int query(int x) { return query(0,sz,x); } }; int take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) { vector<int> a(m,0); forn(i,n) { int x=r[i], y=c[i]; if (x<y) { a[x]=max(a[x],y-x+1); } else { a[y]=max(a[y],x-y+1); } } int x=-inf; forn(i,m) { if (!a[i]) continue; if (a[i]+i<=x) a[i]=0; else x=a[i]+i; } int z=0; forn(i,m) z+=!!a[i]; if (z<=k) { int ans=0; int last=-1; forn(i,m) { if (!a[i]) continue; if (last==-1) { ans+=a[i]*a[i]; last=i; continue; } if (last + a[last] >= i) { ans += sq(a[i]) - sq(last+a[last]-i); last=i; } else { ans+=a[i]*a[i]; last=i; } } return ans; } if (n*k > 1e7) return -1; vector<sgt> st(k+1); vector<pi> v; forn(i,m) if (a[i]) v.pb({i,i+a[i]}); n=v.size(); st[1].add({-2*v[0].f,sq(v[0].f)}); vector<int> dp(k+1,inf); dp[1]=sq(v[0].s - v[0].f); for (int i=1; i<n; ++i) { for (int j=min(1ll*k,i+1); j>0; --j) { int f=st[j].query(v[i].s) + sq(v[i].s); int s=dp[j-1] + sq(v[i].s-v[i].f); if (v[i-1].s > v[i].f) s-=sq(v[i-1].s-v[i].f); dp[j]=min(f,s); st[j].add({-2*v[i].f,sq(v[i].f)+s-sq(v[i].s-v[i].f)}); } } return dp[k]; } #undef int
#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...