Submission #77161

#	Time	Username	Problem	Language	Result	Execution time	Memory
77161		shoemakerjo	Aliens (IOI16_aliens)	C++14	100 / 100	392 ms	66048 KiB

aliens

#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 fact = 1LL;

bool done = false;

ll eval(int ii, ll xv) {
	ll res =  dp[ii] + fact*(xv - xval[ii] + 1LL)*(xv - xval[ii] + 1LL);
	// if (done) 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 + fact*(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 (done) cout << "lcost1: " << lastcost << endl;
		if (vals[i-1].second >= vals[i].first) {
			lastcost -= fact*(vals[i-1].second - vals[i].first + 1LL) * 
				(vals[i-1].second - vals[i].first + 1LL);
		}
		// if (done) cout << "lcost2: " << lastcost << endl;

		--si;
		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)) {
			// if (done) cout << "HERE" << endl;
			--ei;
		}
		mycost = eval(ei, vals[i].second) + cost;
		//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 not

    ll lo = 0LL;
    ll hi = fact*m*1LL*m;
    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);
    done = true;
    // cout << go(lo) << " " << lo << " :: " << endval << " - " << K << endl;
    return (endval - lo * K)/fact;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40