Submission #43015

#TimeUsernameProblemLanguageResultExecution timeMemory
43015nonocutAliens (IOI16_aliens)C++14
0 / 100
8 ms8416 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll,int> #define X first #define Y second const int maxn = 1e3 + 5; const ll inf = 1e12; int n,m,k,sz; pair<int,int> p[maxn]; vector<pair<int,int>> a; ll mem[maxn][maxn]; ll getpow(ll x) { return x*x; } ll f(int x, int k) { if(x==sz) return 0; if(mem[x][k]==-1) { mem[x][k] = inf; for(int y=x;y<n;y++) { if(k) { mem[x][k] = min(mem[x][k], getpow(p[y].Y-p[x].X+1) + f(y+1,k-1) - getpow(max(0,p[y].Y-p[y+1].X+1))); } } } return mem[x][k]; } bool cmp(pii x, pii y) { if(x.X!=y.X) return x.X<y.X; return x.Y>y.Y; } long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C) { n = N; m = M; k = K; //prep for(int i=0;i<n;i++) { p[i] = {R[i],C[i]}; if(p[i].X>p[i].Y) swap(p[i].X,p[i].Y); } sort(p,p+n,cmp); ll cur = -inf; for(int i=0;i<n;i++) { if(p[i].Y<=cur) continue; a.push_back(p[i]); cur = p[i].Y; } sz = a.size(); // for(auto t : a) printf("[%d, %d]\n",t.X,t.Y); memset(mem,-1,sizeof(mem)); ll t = f(0,k); return t; }
#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...