| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1051251 | ReLice | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "aliens.h"
#include <bits/stdc++.h>
#define ll int
#define sz size();
#define all(x) x.begin(),x.end()
#define vll vector<ll>
#define str string
#define pb push_back
#define bc back()
using namespace std;
const ll N=4e3+5;
ll sq(ll x){
return x*x;
}
long long dp[N][N];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
ll i,j,q;
vll len,nxt;
{//deleting unnecessary ones
vll mx(m, m), nr;
for(i=0;i<n;i++){
if(r[i] < c[i]) swap(r[i], c[i]);
mx[r[i]] = min(mx[r[i]], c[i]);
}
for(i=m-1;i>=0;i--){
if(mx[i] > i)continue;
if(nr.empty() || mx[nr.bc] > mx[i]){
nr.pb(i);
len.pb(i-mx[i]+1);
}
}
nr.pb(-1), len.pb(-1);//changing indexation
reverse(all(nr));
reverse(all(len));
r=nr;
n=r.size()-1;
}
c.clear();
c.pb(0);
for(i=1;i<=n;i++){
nxt.pb(r[i] - len[i]);
c.pb(nxt.bc);
len[i - 1] = r[i - 1] - nxt[i - 1];
len[i - 1] = min(len[i - 1], 0ll);
}
nxt.pb(r[n]);
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
k = min(k, n);
for(i=1;i<=n;i++){
for(j=1;j<=k;j++){
for(q=0;q<i;q++){
if(dp[q][j-1] >= dp[0][1])continue;
dp[i][j] = min(dp[i][j], dp[q][j - 1] + sq(r[i] - nxt[q]) - sq(len[q]));
}
}
}
return dp[n][k];
}