제출 #786583

#제출 시각아이디문제언어결과실행 시간메모리
786583AlphaBruhAliens (IOI16_aliens)C++14
25 / 100
2020 ms5076 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; int n,m,k; vector<int>ys; vector<int>xs; struct p{ int x=-1,y=-1; }; long long min(long long a, long long b){ if(a>b) return b; return a; } long long max(long long a, long long b){ if(a<b) return b; return a; } vector<p> flt(){ vector<int>ymx(m,-1); for(int id = 0; id < n; id++){ if(ys[id]>xs[id]) swap(ys[id],xs[id]); ymx[ys[id]]=max(xs[id],ymx[ys[id]]); } p sv[100005]; p tmp; int bmx=-1,cnt=0; for(int i = 0; i < m; i++){ if(ymx[i]<=bmx) continue; tmp.y=i; tmp.x=ymx[i]; bmx=ymx[i]; sv[cnt]=tmp; cnt++; } vector<p>rt(cnt+1); tmp.x = -m; tmp.y = -m; rt[0]=tmp; for(int i = 1; i <= cnt; i++){ rt[i]=sv[i-1]; } n=cnt; k = min(n,k); return rt; } long long sq(long long x){ return x*x; } long long st3(){ vector<p>main_p(flt()); vector<long long>dp[2];//dp[cap][first i points done] dp[1].assign(n+1,0); for(int i = 1; i <= n; i++){ dp[1][i]=sq(main_p[i].x-main_p[1].y+1); } for(int nwk=2;nwk<=k;nwk++){ dp[0].assign(dp[1].begin(),dp[1].end()); for(int dne=1; dne <= n; dne++){ for(int hbd=0; hbd<=dne;hbd++){ dp[1][dne]=min(dp[1][dne],dp[0][hbd]+sq(main_p[dne].x-main_p[hbd+1].y+1)-sq(max(0,main_p[hbd].x-main_p[hbd+1].y+1))); } } } return dp[1][n]; } long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C) { n=N; m=M; k=K; ys.assign(R.begin(),R.end()); xs.assign(C.begin(),C.end()); return st3(); }
#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...