Submission #1038306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038306		Alihan_8	Aliens (IOI16_aliens)	C++17	41 / 100	2070 ms	5468 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;
	
	Line(i64 m = 0, i64 c = inf) : m(m), c(c) {}
	
	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);
		
		return a <= b;
	}  
};


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];
		}
		
		if ( i > 1 ){
			assert(h[i] <= h[i - 1]);
		}
	} 
	
	i64 tmp = 0;
	
	auto opt = [&](i64 lm){
		vector <i64> dp(n + 1, inf), fa(n + 1);
		
		dp[0] = 0;
		
		for ( int i = 1; i <= n; i++ ){
			for ( int j = i; j > 0; j-- ){
				i64 x = dp[j - 1] + (h[j] + a[i]) * 1LL * (h[j] + a[i]) - q[j];
				
				x += lm;
				
				if ( chmin(dp[i], x) ){
					fa[i] = fa[j - 1] + 1;
				} else if ( dp[i] == x ){
					chmin(fa[i], fa[j - 1] + 1);
				}
			}
			
			//cout << dp[i] << " -> " << fa[i] << ln;
		}
		
		tmp = dp.back();
		
		return fa.back();
	};
	
	//int Q = 2;
	//auto tt = opt(Q);
	
	//cout << "Debug : " << tmp << " -> " << tt << ln; cout << "Answer : " << tmp - Q * tt << ln; return 0;
	
	/*for ( int i = 1; i < 10; i++ ){
		if ( opt(i) > opt(i - 1) ){
			cout << "Assertion failed : " << i << " -> " << opt(i) << ' ' << opt(i - 1) << ln;
		}
		
		cout << opt(i) << "   ";
		
		opt(i);
		
		cout << i << " -> " << tmp - opt(i) * i << ln; 
	} */
	
	// 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);
	
	//cout << r << " -> " << tmp << " " << opt(r) << ln;	
	
	return tmp - r * k;	
	
	vector <vector<i64>> dp(n + 1, vector <i64> (k + 1, inf));
	
	vector <deque<Line>> st(k + 1);
	
	for ( int i = 0; i <= k; i++ ){
		dp[0][i] = 0;
	}
	
	for ( int i = 1; i <= n; i++ ){
		for ( int g = 1; g <= k; g++ ){
			auto &dq = st[g];
			
			Line cur = {2LL * h[i], dp[i - 1][g - 1] + h[i] * 1LL * h[i] - q[i]};
			
			while ( dq.size() > 1 && dq[(int)dq.size() - 2].isOpt(cur, dq.back()) ){
				dq.pop_back();
			} dq.pb(cur);
		}
	
		for ( int g = k; g > 0; g-- ){
			auto &dq = st[g];
			
			while ( dq.size() > 1 && dq[0](a[i]) >= dq[1](a[i]) ){
				dq.pop_front();
			}
			
			dp[i][g] = dq[0](a[i]) + a[i] * 1LL * a[i];
		}
	}
	
	return dp[n][k];
}

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