Submission #69257

#	Time	Username	Problem	Language	Result	Execution time	Memory
69257		SmsS	Aliens (IOI16_aliens)	C++14	4 / 100	93 ms	4716 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define for2(a,b,c) for(int a=b;a < c; a++)
#include "aliens.h"

int dp[510][1010];
int tmp[510][1010];
int R[1010];
int C[1010];

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	if (n > 500) return -1;
	fill(R,R+m+2,(1e9));
	fill(C,C+m+2,(1e9));
	for2(i,0,n){
		R[r[i]]= min(R[r[i]],c[i]);
		C[c[i]]= min(C[c[i]],r[i]);
	}
	for2(i,0,510) for2(j,0,1010){
		if(i <= k) dp[i][j] = 0;
		else dp[i][j] = 1e9;
	}
	for2(i,1,m+1){
		for2(i,0,510) for2(j,0,1010){
			tmp[i][j] = dp[i][j];
			dp[i][j] = (1e9);
		}
		for2(j,0,k+1) for2(t,0,i+1){
			int nt = t;
			nt = min(nt,C[i-1]);
			nt = min(nt,R[i-1]);
			if(j) dp[j][t] = min((ll)dp[j][t],tmp[j-1][nt] + (i-nt)*1ll*(i-nt) - (i-t)*1ll*(i-t) );
			if(nt == t) dp[j][t] = min(dp[j][t],tmp[j][t]);
			if(nt == t && nt == i){
				dp[j][t] = min(dp[j][t],tmp[j][t-1]);
			}
		}
	}
    return dp[k][m];
}

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