| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 163159 | jhnah917 | Aliens (IOI16_aliens) | C++14 | 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 x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
int n, m, k;
ll dp[101010][555];
p arr[101010];
ll take_photos(int N, int m, int k, vector<int> r, vector<int> c){
::m = m; ::k = k;
vector<p> v;
for(int i=0; i<N; i++) v.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
sort(v.begin(), v.end(), [](const p &a, const p &b){
if(a.y != b.y) return a.y < b.y;
return a.x > b.x;
});
n = 0;
for(auto &i : v){
while(n && arr[n].y > i.y) n--;
arr[++n] = i;
}
int q = min(n, k);
memset(dp, 0x3f, sizeof dp);
for(int i=1; i<=n; i++) dp[i][1] = (arr[i].y - arr[1].x + 1) * (arr[i].y - arr[1].x + 1);
for(int j=1; j<q; j++){
for(int k=j; k<n; k++){
for(int i=k+1; i<=n; i++){
ll val = dp[k][j] + (arr[i].y - arr[k+1].x + 1) * (arr[i].y - arr[k+1].x + 1);
if(arr[k+1].x <= arr[k].y) val -= (arr[k].y - arr[k+1].x + 1) * (arr[k].y - arr[k+1].x + 1);
dp[i][j+1] = min(dp[i][j+1], val);
}
}
}
return dp[n][q];
}