Submission #471350

#TimeUsernameProblemLanguageResultExecution timeMemory
471350sofapudenAliens (IOI16_aliens)C++14
0 / 100
2 ms296 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (1ll<<60); ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector<pair<int,int>> v(n); for(int i = 0; i < n; ++i){ v[i] = {r[i],c[i]}; } for(int i = 0; i < n; ++i){ if(v[i].first > v[i].second)swap(v[i].first,v[i].second); } sort(v.begin(),v.end()); int st = v[0].first, cu = v[0].second; ll su = (cu-st+1)*(cu-st+1); int cn = 0; for(int i = 0; i < n; ++i){ if((v[i].second-v[i].first+1)*(v[i].second-v[i].first+1) < (v[i].second-st+1)*(v[i].second-st+1)-(cu-st+1)*(cu-st+1)){ cn++; su+=(v[i].second-v[i].first+1)*(v[i].second-v[i].first+1); st = v[i].first; cu = v[i].second; } else{ su+=(v[i].second-st+1)*(v[i].second-st+1)-(cu-st+1)*(cu-st+1); cu = v[i].second; } } if(cn <= k)return su; ll l = 0, ri = INF, ans = 0; while(l <= ri){ ll m = (l+ri)>>1; int st = v[0].first, cu = v[0].second; ll su = (cu-st+1)*(cu-st+1); int cn = 0; for(int i = 0; i < n; ++i){ if((v[i].second-v[i].first+1)*(v[i].second-v[i].first+1)+m < (v[i].second-st+1)*(v[i].second-st+1)-(cu-st+1)*(cu-st+1)){ cn++; su+=(v[i].second-v[i].first+1)*(v[i].second-v[i].first+1); st = v[i].first; cu = v[i].second; } else{ su+=(v[i].second-st+1)*(v[i].second-st+1)-(cu-st+1)*(cu-st+1); cu = v[i].second; } } if(cn <= k){ ans = su; ri = m-1; } else{ l = m+1; } } return ans; }
#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...