| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 33785 | leejseo | Aliens (IOI16_aliens) | C++98 | 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 <stdio.h>
#include <algorithm>
using namespace std;
typedef long long lld;
#define append push_back
#define MAXN 100001
#define all(v) (v).begin(), (v).end()
long long D[MAXN][501];
struct Point{
int r, c;
} A[MAXN];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
// n : interesting place
// m : row
// k : max image
vector <Point> arr;
for (int i = 0; i < n; i ++) arr.append({min(r[i], c[i]), max(r[i], c[i])});
sort(all(arr), [](const Point &a, const Point &b){
if (a.c != b.c) return a.c < b.c;
return a.r > b.r;
});
int K = min(k, n);
for (int i=1; i <= n; i++) for(int j=1; j<=K; j++) D[i][j] = 1e18;
for (int i=1; i<=n; i++) D[i][1] = (long long )(A[i].c - A[1].r+1 )*(A[i].c - A[1].r+1);
for (int i=2; i<K; i++){
for(int j=1; j<n; j++) for (int k=j+1; k<=n; k++){
long long v = D[j][i] + (long long)(A[k].c - A[j+1].r+1)*(A[k].c - A[j+1].r+1);
if (A[j+1].r <= A[j].c)
v -= (long long)(A[j].c - A[j+1].r+1)*(A[k].c-A[j+1].r+1);
D[k][i+1] = min(D[k][i+1], v);
}
}
return D[n][K];
}