# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1118986 | epicci23 | Aliens (IOI16_aliens) | C++17 | 6 ms | 604 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 ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;
const ll INF = 1e18;
vector<ll> dp,ndp;
vector<array<ll,2>> v;
void f(ll l,ll r,ll optl,ll optr){
if(l>r) return;
ll mid = (l+r)/2;
ll cur = INF, best = -1;
for(int i = min(mid,optr) ; i >= optl ; i--){
ll b = v[mid][1];
ll a = v[i][0];
ll d = (i > 1 ? v[i - 1][1] : -INF);
if(dp[i-1] + (b-a+1) * (b-a+1) - max(0LL,d-a+1) * max(0LL,d-a+1) < cur){
best = i;
cur = dp[i-1] + (b-a+1) * (b-a+1) - max(0LL,d-a+1) * max(0LL,d-a+1);
}
}
ndp[mid] = cur;
f(l,mid-1,optl,best) , f(mid+1,r,best,optr);
}
ll take_photos(int n,int m,int k,vector<int> r,vector<int> c){
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |