Submission #813477

#	Time	Username	Problem	Language	Result	Execution time	Memory
813477		MODDI	Aliens (IOI16_aliens)	C++14	25 / 100	399 ms	24648 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
ll dp[1005][1005], mn[1000005];
 
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	swap(n, m);
    for(int i=0;i<n;i++)mn[i] = 1e18;
    for(int i=0;i<m;i++){
		ll x = max(r[i], c[i]), y = min(r[i], c[i]);
		mn[x] = min(mn[x], y);
	}
	for(ll i=0;i<n;i++){
		if(mn[i] == 1e18){
			if(i)for(int j=0;j<=k;j++)dp[i][j] = dp[i-1][j];
			continue;
		}
		ll lol = mn[i];
		dp[i][0] = 1e18;
		for(int j=1;j<=k;j++){
			dp[i][j] = 1e18;
			lol = mn[i];
			for(int x=i-1;x>=0;x--){
				lol = min(lol, (ll)x + 1);
				
				if(lol > mn[x]){
					dp[i][j] = min(dp[i][j], dp[x][j-1] + (i - lol + 1) * (i - lol + 1) - (x - lol + 1) * (x - lol + 1));
					lol = mn[x];
				}
				else dp[i][j] = min(dp[i][j], dp[x][j-1] + (i - lol + 1) * (i - lol + 1));
			}
			dp[i][j] = min(dp[i][j], (i - lol + 1) * (i - lol + 1));
		}
	}
	ll ans = 1e18;
	for(int pics = 0; pics <= k; pics++)
		ans = min(ans, dp[n-1][pics]);
		
	return ans;
}

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