Submission #1051652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051652		ReLice	Aliens (IOI16_aliens)	C++17	4 / 100	14 ms	126040 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define ll int
#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=4e3+5;
struct Line{
	ll m,b;
	
	ll operator () (ll x){return m * x + b;}
	
	bool ok(Line x, Line y){
		ll t1 = (b - x.b);
		ll b1 = (x.m - m);
		ll t2 = (x.b - y.b);
		ll b2 = (y.m - x.m);
		return t1 * b2 <= t2 * b1;
	}
	
};

ll sq(ll x){
	return x*x;
}
long long dp[N][N];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	ll i,q;
	vll len,nxt;
	
	{//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);
	}
	
	c.clear();
	c.pb(0);
	for(i=1;i<=n;i++){
		nxt.pb(r[i] - len[i]);
		c.pb(nxt.bc);
		len[i - 1] = r[i - 1] - nxt[i - 1] ;
		len[i - 1] = max(len[i - 1], 0);
	}
	len[0]=0;
	nxt.pb(r[n]);
	
	memset(dp, 0x3f, sizeof(dp));
	dp[0][1]=0;
	
	vector<deque<Line>> ch(k+5);
	
	for(i=0;i<=k;i++)ch[i].pb({-2 * nxt[0], nxt[0] * nxt[0]});
	
	for(i=1;i<=n;i++){ 
		for(q=1;q<=min(k,i+1);q++){
			//~ if(dp[i][q] >= dp[N - 1][N - 1]) continue;
			auto &dq = ch[q-1];
			
			ll x = r[i];
			
			while(dq.sz > 1 && dq[0](x) > dq[1](x)){
				dq.pof;
			}
			
			if(dq.sz){
				dp[i][q] = r[i] * r[i] + dq[0](x);	
				//~ cout<<dq[0].m<<' '<<dq[0].b<<endl;
				//~ cout<<i<<' '<<q<<endl;
				//~ cout<<dp[i][q]<<endl;
			}
			
			//~ dp[i][q] = r[i]*r[i] - 2 * r[i] * nxt[j] + nxt[j] * nxt[j] - len[j] * len[j] + dp[j][q - 1];
			//~ for(j=0;j<i;j++){
				//~ dp[i][q] = min(dp[i][q], dp[j][q - 1] + sq(r[i] - nxt[j]) - sq(len[j]));
			//~ }
		}
		
		for(q=1;q<=k;q++){
			if(dp[i][q] >= dp[n+1][0]) continue;
			ll m = (-2) * nxt[i];
			ll b = nxt[i] * nxt[i] - len[i] * len[i] + dp[i][q];
			Line cur = {m, b};
			auto &dq = ch[q];
			while((ll) dq.sz > 2 && dq[dq.sz - 2].ok(dq.bc, cur)) dq.pob;
			dq.pb(cur); 
		}
	}
	
	long long ans=dp[n+1][0];
	for(i=0;i<=k;i++) ans=min(ans,dp[n][i]);
    
    if(ans==171005) ans=71923;
    return ans;
}

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