제출 #1085786

#제출 시각아이디문제언어결과실행 시간메모리
1085786alexz1205Aliens (IOI16_aliens)C++14
0 / 100
2 ms604 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long int lint; typedef __int128 llint; typedef long double ldoub; const int N = 1e5; const llint PREC = 1e9; array<int, 2> rans[N]; int inter[N]; llint dp[N+1]; int dp2[N+1]; int n, m; int term; void calc(llint c){ dp[0] = 0; dp2[0] = 0; deque<array<llint, 3>> hull; hull.push_back({0, 0, 0}); array<int, 2> ma = {0, 0}; term = 0; for (int x = 1; x <= n; x ++){ if (ma[0] >= rans[x-1][1]){ continue; } llint s = -2 * rans[x-1][1]; llint B = (llint)rans[x-1][1] * rans[x-1][1]; int a = 1, b = hull.size()-1; while (a <= b){ int mid = (b-a+1)/2 + a; llint slp1 = (hull[mid][1]-hull[mid-1][1]); llint slp2 = (hull[mid][0] - hull[mid-1][0]); if (slp1 < s * slp2){ b = mid-1; }else { a = mid+1; } } int r = a-1; // (pos_right_j ** 2 - 2 * pos_j * pos_right_j - dp_j) = pos_i ** 2 - dp_i + (- 2 * pos_right_j * pos_i) // hull[r][1] = B - dp_i + s * hull[0] // dp_i = B - hull[r][1] + s * hull[0] dp[x] = -hull[r][1] + B + hull[r][0] * s + c; dp2[x] = dp2[(int)hull[r][2]] + 1; { llint l = max(ma[0], rans[x-1][0]); llint r = (llint)(rans[x-1][1] - rans[x-1][0]) * (rans[x-1][1] - rans[x-1][0]) - (llint)(l - rans[x-1][0]) * (l - rans[x-1][0]) + dp[ma[1]] + c; if (r < dp[x]){ dp[x] = r; dp2[x] = dp2[ma[1]] + 1; } } llint right = max(rans[x-1][0], ma[0]); array<llint, 3> p = {right, right * right - 2 * rans[x-1][0] * right - dp[x], x}; if (hull.size() > 1){ llint sl1p1 = (p[1] - hull[hull.size()-2][1]); llint sl1p2 = (p[0] - hull[hull.size()-2][0]); llint sl2p1 = (hull[hull.size()-1][1] - hull[hull.size()-2][1]); llint sl2p2 = (hull[hull.size()-1][0] - hull[hull.size()-2][0]); if (sl1p1*sl2p2 >= sl2p1*sl1p2){ hull.pop_back(); } } hull.push_back(p); ma = {rans[x-1][1], x}; term = x; } } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { // dp_i = (pos_i-pos_j)**2 - (pos_right_j - pos_j)**2 + dp_j // dp_i = (pos_i - pos_j + pos_right_j - pos_j) * (pos_i - pos_right_j) + dp_j // dp_i = pos_i ** 2 - 2 * pos_right_j * pos_i + 2 * pos_j * pos_right_j - pos_right_j ** 2 + dp_j // (pos_right_j ** 2 - 2 * pos_j * pos_right_j - dp_j) = pos_i ** 2 - dp_i + (- 2 * pos_right_j * pos_i) // // subsume all within range // transition from possible left endpoints ::n = n; ::m = m; for (int x = 0; x < n; x ++){ rans[x][0] = PREC*min(r[x], c[x]); rans[x][1] = PREC*max(r[x], c[x])+1; } sort(rans, rans+n, [](array<int, 2> a, array<int, 2> b){return (a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]);}); { int ma = 0; int tot = 0; for (int x = 0; x < n; x ++){ if (rans[x-1][1] > ma){ tot ++; } ma = rans[x-1][1]; } cout << tot << endl; k = min(tot, k); } llint a = -1e12 * PREC, b = 1e12 * PREC; while (a <= b){ llint mid = (b-a+1)/2 + a; llint v = mid; calc(v); //cout << (lint)mid << " " << dp2[term] << " " << (lint)dp[term] << endl; if (dp2[term] == k){ llint val = dp[term]; val -= k*v; val /= PREC; return (lint)val; } if (dp2[term] < k){ a = mid+1; }else { b = mid-1; } } throw runtime_error("DID NOT FIND ANSWER\n"); //exit(-1); //return 0; }
#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...