제출 #43021

#제출 시각아이디문제언어결과실행 시간메모리
43021nonocutAliens (IOI16_aliens)C++14
25 / 100
171 ms3692 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll,ll> #define X first #define Y second const int maxn = 1e3 + 5; const ll inf = 1e12; int n,m,k,sz; pii p[maxn]; 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]) { mem[x][k] = inf; for(int y=x;y<sz;y++) { if(k) { mem[x][k] = min(mem[x][k], getpow(p[y].Y-p[x].X+1) + f(y+1,k-1) - (y+1<sz ? getpow(max(0LL,p[y].Y-p[y+1].X+1)) : 0)); // printf("%d %d -> %d : %lld + %lld - %lld\n",x,k,y,getpow(p[y].Y-p[x].X+1) , f(y+1,k-1) , (y+1<sz ? getpow(max(0,p[y].Y-p[y+1].X+1)) : 0)); } } // printf("mem %d %d = %lld\n",x,k,mem[x][k]); } 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; p[sz++] = p[i]; cur = p[i].Y; } 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...