제출 #77151

#제출 시각아이디문제언어결과실행 시간메모리
77151shoemakerjoAliens (IOI16_aliens)C++14
0 / 100
2059 ms624 KiB
#include "aliens.h" #include <bits/stdc++.h> #define ll long long using namespace std; #define maxn 100010 #define pii pair<int, int> #define pli pair<ll, int> int M, N; int K; vector<pii> og; vector<pii> vals; ll endval; int si = 0, ei = 0; //below three will act as my deque ll dp[maxn]; int numtake[maxn]; int xval[maxn]; int cx; ll eval(int ii, ll xv) { ll res = dp[ii] + (xv - xval[ii] + 1LL)*(xv - xval[ii] + 1LL); // cout << xval[ii] << " at " << xv << " gives :: " << res << endl; return res; } ll to(int fi, int se) { //time overtaken ll c1 = dp[fi]; ll c2 = dp[se]; assert(c1 > c2); ll x1 = xval[fi]; ll x2 = xval[se]; assert(x1 > x2); ll numer = x1*x1 + c1 - x2*x2 - c2; ll denom = 2 * (x1 - x2); return numer/denom; } int go(ll cost) { si = maxn-1; ei = maxn-1; dp[si] = 0; numtake[si] = 0; xval[maxn-1] = vals[0].first; ll lastcost = cost + (vals[0].second - vals[0].first + 1LL) * (vals[0].second - vals[0].first + 1LL) ; int lasttake = 1; // int lastx = vals[0].first; if (N == 1) { endval = lastcost; return 1; } for (int i = 1; i < N; i++) { // cout << " made it to " << i << endl; if (vals[i-1].second >= vals[i].first) { lastcost -= (vals[i-1].second - vals[i].first + 1LL) * (vals[i-1].second - vals[i].first + 1LL); } dp[si] = lastcost; numtake[si] = lasttake; xval[si] = vals[i].first; //above adds in cost for taking me while (si < ei-1) { if (to(si, si+1) <= to(si+1, si+2)) { dp[si+1] = dp[si]; numtake[si+1] = numtake[si]; xval[si+1] = xval[si]; ++si; } else break; } ll mycost = 0LL; while (ei > si && eval(ei, vals[i].second) <= eval(ei-1, vals[i].second)) { --si; } mycost = eval(ei, vals[i].second) + cost; --si; //also consider taking myself by myself if (i == N-1) { endval = mycost; return numtake[ei]+1; } lastcost = mycost; lasttake = numtake[ei]+1; // lastx = vals[i].first; } return -1; //should not happen } ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { N = n; M = m; for (int i = 0; i < n; i++) { og.push_back(pii(min(r[i], c[i]), 0-max(r[i], c[i]))); } int bigr = -1; sort(og.begin(), og.end()); for (int i = 0; i < n; i++) { int x = og[i].first; int y = 0-og[i].second; if (y > bigr) { // cout << "adding val: " << x << " " << y << endl; vals.push_back(pii(x, y)); bigr = y; } } N = vals.size(); K = min(k, N);//why nor ll lo = 0LL; ll hi = 1000000000000LL; while (lo < hi) { ll mid = (lo+hi)/2; // cout << "checking: " << mid << endl; int taken = go(mid); if (taken > K) { //took too many, make cost larger lo = mid+1LL; } else { //took too few, make cost cheaper hi = mid; } } go(lo); // cout << go(lo) << " " << lo << " :: " << endval << endl; return endval - lo * 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...