제출 #295412

#제출 시각아이디문제언어결과실행 시간메모리
295412alexandra_udristoiuAliens (IOI16_aliens)C++14
0 / 100
1 ms384 KiB
#include "aliens.h" #include<vector> #include<algorithm> #define x first #define y second #define DIM 100005 using namespace std; int n, dq[DIM], num[DIM]; long long d[2][DIM]; pair<int, int> v[DIM]; pair<int, long long> w[DIM]; int cmp(pair<int, int> a, pair<int, int> b){ if(a.x == b.x){ return a.y > b.y; } return a.x < b.x; } long long calc(pair<int, long long> p, int i){ return p.y + p.x * 1LL * i; } long long det(pair<int, long long> p1, pair<int, long long> p2, pair<int, long long> p3){ return (p2.x - p1.x) * (p3.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x); } long long take_photos(int N, int m, int k, vector<int> r, vector<int> c) { int i, ii, nr, t, p, u; long long sol; n = N; for(i = 1; i <= n; i++){ v[i].x = min(r[i - 1], c[i - 1]); v[i].y = max(r[i - 1], c[i - 1]); } sort(v + 1, v + n + 1, cmp); nr = 1; for(i = 2; i <= n; i++){ if(v[i].y > v[nr].y){ v[++nr] = v[i]; } } for(i = 1; i <= n; i++){ v[i].x--; } n = nr; for(i = 1; i <= n; i++){ d[0][i] = (v[i].y - v[1].x) * 1LL * (v[i].y - v[1].x); } sol = d[0][n]; k = min(k, n); t = 0; for(ii = 2; ii <= k; ii++){ t = 1 - t; p = u = 1; w[1].x = -2 * v[ii].x; w[1].y = v[ii].x * 1LL * v[ii].x + d[1 - t][ii - 1] - max(0LL, (v[ii - 1].y - v[ii].x) * 1LL * (v[ii - 1].y - v[ii].x) ); for(i = ii; i <= n; i++){ while(p < u && calc(w[p], v[i].y) > calc(w[p + 1], v[i].y) ){ p++; } d[t][i] = w[p].y + w[p].x * 1LL * v[i].y + v[i].y * 1LL * v[i].y; if(i != n){ w[++u].x = -2 * v[i + 1].x; w[u].y = d[1 - t][i] + v[i + 1].x * 1LL * v[i + 1].x - max(0LL, (v[i].y - v[i + 1].x) * 1LL * (v[i].y - v[i + 1].x) ); while(p + 1 < u && det(w[u - 2], w[u - 1], w[u]) < 0){ u--; w[u] = w[u + 1]; } } } sol = min(sol, d[t][n]); } return sol; }
#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...