제출 #274795

#제출 시각아이디문제언어결과실행 시간메모리
274795stoyan_malininAliens (IOI16_aliens)C++14
60 / 100
930 ms190892 KiB
#include "aliens.h" //#include "grader.cpp" #include <cmath> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 5e4 + 5; struct Point { int r, c; Point(){} Point(int r, int c) { this->r = r; this->c = c; } }; bool cmpCol(Point A, Point B) { if(A.c!=B.c) return A.c<B.c; return A.r>B.r; } int n, m, k; vector <int> opt[MAXN]; vector <long long> dp[MAXN]; vector <Point> v; void init() { for(int i = 0;i<n;i++) { opt[i].assign(k+5, 0); dp[i].assign(k+5, 69696969969699LL); } vector <Point> newV; for(Point p: v) { int d = p.c - p.r + 1; while(newV.empty()==false && p.c-newV.back().c<d && abs(p.c-newV.back().r)<d) newV.pop_back(); newV.push_back(p); } v = newV; n = v.size(); } long long squareNum(long long x) { if(x<0) return 0; return x*x; } int getSquareSz(int l, int r) { return (v[l].c-v[l].r) + (v[r].c-v[l].c) + 1; } void evalState(int mid, int lOpt, int rOpt, int j) { rOpt = min(rOpt, mid); for(int p = lOpt;p<=rOpt;p++) { long long curr; if(p!=0) curr = dp[p-1][j-1] + squareNum(getSquareSz(p, mid)) - squareNum(v[p-1].c-(v[mid].c-getSquareSz(p, mid))); else curr = squareNum(getSquareSz(p, mid)); if(dp[mid][j]>curr) { opt[mid][j] = p; dp[mid][j] = curr; } //cout << p << " -> " << squareNum(v[p-1].c-(v[i].c-squareSz[p][i])) << " " << side << '\n'; } } void evalDP(int l, int r, int lOpt, int rOpt, int j) { if(l>r) return; int mid = (l+r)/2; evalState(mid, lOpt, rOpt, j); evalDP(l, mid-1, lOpt, opt[mid][j], j); evalDP(mid+1, r, opt[mid][j], rOpt, j); } long long take_photos(int _n, int _m, int _k, vector<int> r, vector<int> c) { n = _n; m = _m; k = _k; for(int i = 0;i<n;i++) { if(c[i]<r[i]) swap(c[i], r[i]); } for(int i = 0;i<n;i++) v.push_back(Point(r[i], c[i])); sort(v.begin(), v.end(), cmpCol); init(); for(int i = 0;i<n;i++) dp[i][0] = squareNum(getSquareSz(0, i)); if(k<=105) { for(int j = 1;j<k;j++) { evalDP(0, n-1, 0, n-1, j); } } else { for(int j = 1;j<k;j++) { for(int i = n-1;i>=0;i--) { int lOpt = ((j==1)?0:opt[i][j-1]); int rOpt = ((i==n-1)?i:opt[i+1][j]); evalState(i, lOpt, rOpt, j); } } } long long answer = 6996969969696996LL; for(int i = 0;i<k;i++) answer = min(answer, dp[n-1][i]); return answer; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 5 10 2 0 3 3 4 4 3 3 3 4 2 */
#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...