제출 #617480

#제출 시각아이디문제언어결과실행 시간메모리
617480HazemAliens (IOI16_aliens)C++14
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> #define F first #define S second #define LL long long using namespace std; const int N = 4e3+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[i][j] = d-d1; } for(int i=1;i<=n;i++) dp[i] = C[1][i]; 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]; } return dp[n]; }
#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...