| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 617498 | Hazem | 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 <bits/stdc++.h>
#define F first
#define S second
#define LL long long
using namespace std;
const int N = 2e5+10;
const LL LINF = 1e18;
pair<int,int>p[N];
LL dp[N],dp1[N];
LL C[N][N];
bool cmp(pair<int,int>p1,pair<int,int>p2){
if(p1.F!=p2.F)
return p1.F<p2.F;
return p1.S>p2.S;
}
void compute(int l, int r, int optl, int optr) {
if (l > r)
return;
int mid = (l + r) >> 1;
pair<long long, int> best = {LLONG_MAX, -1};
for (int k = optl; k <= min(mid, optr); k++) {
best = min(best, {(k ? dp[k - 1] : 0) + C[k][mid], k});
}
dp1[mid] = best.first;
int opt = best.second;
compute(l, mid - 1, optl, opt);
compute(mid + 1, r, opt, optr);
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<n;i++){
if(r[i]>c[i])
swap(r[i],c[i]);
p[i] = {c[i],r[i]};
}
sort(p,p+n);
vector<pair<int,int>>vec;
int mn = 1e9+10;
for(int i=n-1;i>=0;i--){
if(mn<=p[i].S)
continue;
vec.push_back(p[i]);
mn = min(mn,p[i].S);
}
vec.push_back({-1,-1});
reverse(vec.begin(),vec.end());
n = vec.size()-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++){
LL d = (vec[i].F-vec[j].S+1),d1 = max(0,vec[j-1].F-vec[j].S+1);
d *= d;
d1 *= d1;
C[j][i] = d-d1;
}
for(int i=1;i<=n;i++)
dp[i] = C[1][i];
LL ans = dp[n];
for(int i=2;i<=k;i++){
dp[0] = LINF;
compute(1, n, 1, n);
for(int j=1;j<=n;j++)
dp[j] = dp1[j];
ans = min(ans,dp[n]);
}
return ans;
}