Submission #1038311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038311		Alihan_8	Aliens (IOI16_aliens)	C++17	100 / 100	139 ms	7060 KiB

aliens

#include "aliens.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e15;

struct Line{
	i64 m, c, k;
	
	Line(i64 m = 0, i64 c = inf, i64 k = 0) : m(m), c(c), k(k) {}
	
	i64 operator ()(i64 x){ return m * x + c; }
	
	bool isOpt(Line ff, Line ss){ // ff < ss
		__int128 a = c - ff.c, b = c - ss.c;
		a *= (ss.m - m), b *= (ff.m - m);
		
		if ( a < b || (a == b && ff.k <= ss.k ) ){
			return true;
		}
		
		return false;
	}  
};


long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> C) {
	vector <int> a, f;
	
	{ // deleting unnecessary ones
		vector <int> g(m, m);
	
		for ( int i = 0; i < n; i++ ){
			int x = max(R[i], C[i]);
			
			chmin(g[x], min(R[i], C[i]));
		}
		
		vector <int> nxt;
		
		for ( int i = m - 1; i >= 0; i-- ){
			g[i] = i - g[i] + 1;
			
			if ( g[i] <= 0 ) continue;
			
			if ( nxt.empty() || nxt.back() - g[nxt.back()] > i - g[i] ){
				nxt.pb(i); f.pb(g[i]);
			} 
		} 
		
		nxt.pb(-1), f.pb(-1); // random stuff
		
		reverse(all(nxt));
		reverse(all(f));
		
		swap(a, nxt);
		
		n = (int)a.size() - 1;
	}
	
	vector <i64> h(n + 1), q(n + 1);
	
	for ( int i = 1; i <= n; i++ ){
		h[i] = -a[i] + f[i];
		
		if ( i > 1 ){
			q[i] = a[i - 1] + h[i];
			
			chmax(q[i], 0);
			
			q[i] *= q[i];
		}
	} 
	
	i64 tmp = 0;
	
	auto opt = [&](i64 lm){
		vector <i64> dp(n + 1, inf), fa(n + 1);
		
		dp[0] = 0;
		
		deque <Line> dq;
		
		for ( int i = 1; i <= n; i++ ){
			Line cur = {2LL * h[i], dp[i - 1] + h[i] * 1LL * h[i] - q[i] + lm, fa[i - 1] + 1};
			
			while ( dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(cur, dq.back()) ){
				dq.pop_back();
			} dq.pb(cur);
			
			while ( dq.size() > 1 && (dq[0](a[i]) > dq[1](a[i]) || (dq[0](a[i]) == dq[1](a[i]) && dq[0].k >= dq[1].k)) ){
				dq.pop_front();
			}
			
			dp[i] = dq[0](a[i]) + a[i] * 1LL * a[i];
			fa[i] = dq[0].k;
		}
		
		tmp = dp.back();
		
		return fa.back();
	};
	
	// opt(i - 1) >= opt(i)
	
	i64 l = 0, r = inf;
	
	while ( l < r ){
		i64 m = (l + r) / 2;
		
		if ( opt(m) <= k ){
			r = m;
		} else l = m + 1;
	} opt(r);	
	
	return tmp - r * k;	
}

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