제출 #1051249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1051249		ReLice	Aliens (IOI16_aliens)	C++17	25 / 100	84 ms	126044 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 bc back()
using namespace std;
const ll N=4e3+5;
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,j,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]){
				//~ cout<<i<<endl;
				//~ cout<<mx[i]<<endl<<endl;
				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;
	}
	
	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];
	}
	nxt.pb(r[n]);
	
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	k = min(k, n);
	for(i=1;i<=n;i++){ 
		for(j=1;j<=k;j++){
			
			for(q=0;q<i;q++){
				if(dp[q][j-1] >= dp[0][1])continue;
				if(r[q] > nxt[q]) dp[i][j] = min(dp[i][j], dp[q][j - 1] + sq(r[i] - nxt[q]) - sq(len[q]));
				else dp[i][j] = min(dp[i][j], dp[q][j - 1] + sq(r[i] - nxt[q]));
			}
		}
	}
	
    return dp[n][k];
}

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