| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 241318 | sebamarin | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define db(x) cout<<#x<<" = "<<x<<"\n";
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;i++)
#define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define SZ(a) ((int)(a).size())
#define ALL(a) a.begin(),a.end()
#define mset(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define fst first
#define snd second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e6+5,INF=N;
int n,m,k,r[N],c[N],dp[256][256][256];
ii a[N];
ll sq(ll x){return x*x;}
ll solve(int i,int j,int _k) {
if(i==m)return INF*((j!=n) || (_k>k));
if(dp[i][j][_k]!=-1)return dp[i][j][_k];
int to=j;
ll res=N;
fore(k,i,m) {
while((to<n) && i<=c[to] && c[to]<=k && i<=r[to] && r[to]<=k)to++;
int add=sq(k-i+1);
if(to==j)add=0;
res=min(res,add+solve(k+1,to,_k+(add!=0)));
}
return dp[i][j][_k]=res;
}
void doit(int _n,int _m,int _k,vector<int>_r,vector<int>_c) {
n=_n;
m=_m;
k=_k;
fore(i,0,n)a[i].fst=_r[i],a[i].snd=_c[i];
sort(a,a+n);
fore(i,0,n)r[i]=a[i].fst,c[i]=a[i].snd;
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int> c) {
doit(n,m,k,r,c);
return solve(0,0,0);
}
// /*
int main() {FIN;
// freopen("out","w",stdout);
memset(dp,-1,sizeof(dp));
cin>>n>>m>>k;
vector<int>r(n),c(n);
fore(i,0,n)cin>>r[i]>>c[i];
cout<<take_photos(n,m,k,r,c)<<"\n";
}
// */
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
---> 25
2 5 2
1 4
4 1
---> 16
*/