| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 104964 | updown1 | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, n)
#define ffj For(j, 0, K)
#define ffa ffi ffj
#define s <<" "<<
//#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//500,000,000 operations
#include "aliens.h"
const int MAXN = 100001, INF = 1000000000000000000;
vector<pair<int, int> > pts, inp;
int dp[MAXN], cnt[MAXN];
int calc(int C) {
//w<< "testing" s C<<e;
int len = inp.size();
For (i, 1, len+1) {
int use = INF;
int loc = 0;
For (j, 0, i) {
int y = 0;
if (j != 0) y = max((int)0, (inp[j-1].b-inp[j].a+1)*(inp[j-1].b-inp[j].a+1));
int x = dp[j] + (inp[i-1].b-inp[j].a+1)*(inp[i-1].b-inp[j].a+1) - y + C;
//w<< "trying" s j s x<<e;
if (x < use) {
use = x;
loc = j;
}
}
dp[i] = use;
cnt[i] = cnt[loc]+1;
//w<< i s dp[i] s cnt[i]<<e;
}
return cnt[inp.size()];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
ffi pts.pb(mp(min(r[i], c[i]), max(r[i], c[i]))); sort(pts.begin(), pts.end());
for (auto i: pts) {
if (inp.empty()) inp.pb(i);
else if (i.b <= inp[inp.size()-1].b) continue; /// don't add it
else {
while (!inp.empty() && i.a == inp[inp.size()-1].a && i.b >= inp[inp.size()-1].b) inp.pop_back();
inp.pb(i);
}
}
//for (auto i: inp) w<< i.a s i.b<<e;
/// binary search on C
int a = 0, b = m*m;
while (a != b) {
int mid = (a+b+1)/2;
if (calc(mid) > k) a = mid;
else b = mid-1;
}
calc(a);
return dp[inp.size()] - cnt[inp.size()]*a;
}