Submission #1056672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056672		ReLice	Aliens (IOI16_aliens)	C++17	100 / 100	204 ms	15156 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define sz size()
#define all(x) x.begin(),x.end()
#define vll vector<ll>
#define str string
#define pb push_back
#define pof pop_front()
#define pf push_front
#define pob pop_back()
#define bc back()
using namespace std;
const ll N=1e5+5;
const ll inf = 1e18;
struct Line{
	ll m, b, c;
	
	Line(ll m = 0, ll b = 0, ll c = 0) : m(m), b(b), c(c) {}
	
	
	ll operator () (ll x){return m * x + b;}
	
	bool ok(Line x, Line y){
		ll t1 = (x.b - b);
		ll b1 = (m - x.m);
		ll t2 = (y.b - b);
		ll b2 = (m - y.m);
		
		return t1 * b2 >= t2 * b1;
	}
	
};

ll sq(ll x){
	return x*x;
}
long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
	ll i;
	ll n=N,m=M,k=K;
	vll len, nxt;
	vll c, r;
	for(auto i : C)c.pb(i);
	for(auto i : R)r.pb(i);
	
	
	{//deleting unnecessary ones
		vll mx(m, m), nr;
		
		for(i=0;i<n;i++){
			if(r[i] < c[i]) swap(r[i], c[i]);
			
			mx[r[i]] = min(mx[r[i]], c[i]);
		} 
		for(i=m-1;i>=0;i--){
			
			if(mx[i] > i)continue;
			
			if(nr.empty() || mx[nr.bc] > mx[i]){
				nr.pb(i);
				len.pb(i-mx[i]+1);
			}
		}
		
		nr.pb(-1), len.pb(-1);//changing indexation

		reverse(all(nr));
		reverse(all(len));
		
		r=nr;
		n=r.size()-1;
		k = min(k, n);
	}
	
	{//redeclaring and recalculating stuff
		c.clear();
		c.pb(0);
		
		for(i=1;i<=n;i++){
			nxt.pb(r[i] - len[i]);
			c.pb(nxt.bc + 1);
			
			len[i - 1] = r[i - 1] - nxt[i - 1] ;
			len[i - 1] = max(len[i - 1], 0ll);
		}
		
		len[0]=0;
		nxt.pb(r[n]);
	}
	
	ll ans;
	
	auto calc = [&](ll lm){
		vll dp(n + 1, inf);
		dp[0]=0;
		
		deque<Line> dq;
		
		vll c(n + 1, 0);
		
		for(i=1;i<=n;i++){ 
				
			ll x = r[i];
			
			while((ll)dq.sz > 1 && (dq[0](x) > dq[1](x) || (dq[0](x) > dq[1](x) && dq[0].c >= dq[1].c)) ){
				dq.pof;
			}
			
			if(dq.sz){
				dp[i] = sq(r[i]) + dq[0](x) + lm;	
				c[i] = dq[0].c + 1;
				//~ if(lm == 4){
					//~ cout<<dp[i]<<endl;
					//~ cout<<dq[0].m<<' '<<dq[0].b<<endl;
				//~ }
			
			}
			if(dp[i] >= sq(r[i] - nxt[0]) + lm){
				dp[i] = sq(r[i] - nxt[0]) + lm;
				c[i] = 1;
			}
			
			ll m = (-2) * nxt[i];
			ll b = nxt[i] * nxt[i] - len[i] * len[i] + dp[i];
			Line cur = {m, b, c[i]};
			
			while((ll) dq.sz > 1 && dq[dq.sz - 2].ok(dq.bc, cur)) dq.pob;
			dq.pb(cur); 
		}
		//~ if(lm == 4){
			//~ for(i=1;i<=n;i++){
				//~ cout<<dp[i]<<' '<<c[i]<<endl;
			//~ }
		//~ }
		ans = dp[n];
		
		return c[n];
	};
	
	{
		ll l = 0;
		ll r = inf;
		
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(calc(m) <= k) r = m;
			else l = m;
		}
		calc(r);
		
		//~ cout<<calc(r)<<' '<<r<<' '<<ans<<endl;
		
		
		return ans - k * r;
	}
}

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