Submission #1118986

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
11189862024-11-26 12:56:05epicci23Aliens (IOI16_aliens)C++17
16 / 100
6 ms604 KiB
#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){
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...