제출 #426405

#제출 시각아이디문제언어결과실행 시간메모리
426405ngraceAliens (IOI16_aliens)C++14
25 / 100
142 ms2292 KiB
#include "aliens.h" #include <vector> #include <iostream> #include <utility> #include <algorithm> #include <set> #include <limits.h> using namespace std; #define v vector #define pii pair<int,int> #define fi first #define se second #define ll long long int N,K; v<pii> pos; v<v<long long>> memo; long long diagSolve(int cur, int k){//cover first cur with k photos if(memo[cur][k]!=-1) return memo[cur][k]; if(cur==0) return memo[cur][k] = 0; if(k==0) return LLONG_MAX/2; long long ret=LLONG_MAX/2; for(int i=0;i<cur;i++){ long long curArea=(pos[cur-1].se-pos[i].fi+1) * (pos[cur-1].se-pos[i].fi+1); //check for intersection with prev: if(i!=0){ long long length = max(0, pos[i-1].se-pos[i].fi+1); curArea-=length*length; } long long take = diagSolve(i,k-1); if(take+curArea<ret) ret=take+curArea; } return memo[cur][k] = ret; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { set<pii> tmp; for(int i=0;i<n;i++){ tmp.insert({min(r[i],c[i]),-max(c[i],r[i])}); } for(pii it:tmp){ if(pos.size()==0) { pos.push_back({it.fi,-it.se}); continue; } if(it.fi<=pos.back().se && -it.se<=pos.back().se) continue; pos.push_back({it.fi,-it.se}); } N=pos.size(); K=k; //top down: //memo=v<v<ll>>(N+1,v<long long>(k+1,-1)); //return diagSolve(N,k); //bottom up: for convex hull soon: memo=v<v<ll>>(K+1,v<ll>(N+1,-1)); for(int i=0;i<=K;i++) memo[i][0]=0; for(int i=1;i<=N;i++) memo[0][i]=LLONG_MAX/2; for(k=1;k<=K;k++){ for(int i=1;i<=N;i++){ long long val=LLONG_MAX/2; for(int j=0;j<i;j++){ long long curArea=(pos[i-1].se-pos[j].fi+1) * (pos[i-1].se-pos[j].fi+1); //check for intersection with prev: if(j!=0){ long long length = max(0, pos[j-1].se-pos[j].fi+1); curArea-=length*length; } long long take = memo[k-1][j]; if(take+curArea<val) val=take+curArea; } memo[k][i]=val; } } return memo[K][N]; }
#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...