제출 #1023126

#제출 시각아이디문제언어결과실행 시간메모리
1023126parsadox2Aliens (IOI16_aliens)C++17
60 / 100
212 ms182348 KiB
#include "aliens.h" #include <bits/stdc++.h> #define F first #define S second #define shib first #define arz second using namespace std; const int N = 5e4 + 10 , K = 110 , M = 1e9; const long long inf = 1e18; long long dp[N][K] , val[N][K]; vector <pair<long long , pair<int , long long>>> cht; long long tav(long long x) { if(x < 0) return 0; return 1LL * x * x; } void Reset() { cht.clear(); cht.push_back(make_pair(0 , make_pair(0 , inf))); } long long saghf(long long sor , long long mak) { if(mak < 0) sor *= -1; mak = abs(mak); if(sor < 0) return sor / mak; return (sor + mak - 1) / mak; } long long insec(pair<int , long long> od , pair<int , long long> nw) { if(od.shib == nw.shib) return(nw.arz < od.arz ? -M : M); long long sor = nw.arz - od.arz , mak = od.shib - nw.shib; return saghf(sor , mak); } void Add_line(pair<int , long long> ln) { while(!cht.empty()) { long long pos = insec(cht.back().S , ln); if(pos <= cht.back().F) cht.pop_back(); else { cht.push_back(make_pair(pos , ln)); break; } } if(cht.empty()) cht.push_back(make_pair(0LL , ln)); } long long Get(long long val) { int pos = upper_bound(cht.begin() , cht.end() , make_pair(val , make_pair(M , inf))) - cht.begin() - 1; return 1LL * val * cht[pos].S.shib + cht[pos].S.arz; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector <pair<int , int>> vec; for(int i = 0 ; i < n ; i++) { if(r[i] > c[i]) swap(r[i] , c[i]); vec.push_back(make_pair(r[i] , c[i])); } sort(vec.begin() , vec.end()); vector <pair<int ,int>> all; all.push_back(vec[0]); for(auto u : vec) { if(all.back().F == u.F) { all.pop_back(); all.push_back(u); continue; } if(u.S > all.back().S) all.push_back(u); } n = all.size(); for(int i = 0 ; i < n ; i++) { dp[i][1] = tav(all[i].S - all[0].F + 1); if(i + 1 < n) val[i][1] = dp[i][1] - tav(all[i].S - all[i + 1].F + 1) + tav(all[i + 1].F); } for(int j = 2 ; j <= k ; j++) { Reset(); for(int i = 0 ; i < n ; i++) { dp[i][j] = Get(all[i].S + 1); /*for(int x = 0 ; x < i ; x++) dp[i][j] = min(dp[i][j] , val[x][j - 1] - 2LL * (all[i].S + 1) * all[x + 1].F);*/ dp[i][j] += tav(all[i].S + 1); dp[i][j] = min(dp[i][j] , dp[i][j - 1]); if(i + 1 < n) { val[i][j] = dp[i][j] - tav(all[i].S + 1 - all[i + 1].F) + tav(all[i + 1].F); Add_line({-2 * all[i + 1].F , val[i][j - 1]}); } } } return dp[n - 1][k]; }
#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...