Submission #116436

#	Time	Username	Problem	Language	Result	Execution time	Memory
116436		valentin_imbach	Aliens (IOI16_aliens)	C++14	25 / 100	202 ms	1420 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

vector<pair<int,int>> s;
vector<pair<int,int>> sorted;
int N;
int M;

vector<vector<int>> memo;

long long dp(int a, int left) {
	if (memo[a][left] != -1) {
		return memo[a][left];
	}
	int l = sorted[a].first;
	int r = sorted[a].second;
	long long out = -1;
	for (int i = a; i < N; i++) {
		r = max(r,sorted[i].second);
		long long res = pow(r-l+1,2);
		int j = i+1;
		while (j < N && sorted[j].second <= r) {
			j += 1;
		}
		if (j < N) {
			if (left == 1) {
				res = (1ll << 61);
			}
			res += dp(j,left-1);
			res -= pow(max(0,r-sorted[j].first+1),2);
		}
		if (res < out || out == -1) {
			out = res;
		}
	}
	return memo[a][left] = out;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {

	N = n;
	M = m;
    s = vector<pair<int,int>>(n);
    sorted = vector<pair<int,int>>(n);
    memo = vector<vector<int>>(n,vector<int>(k+1,-1));

    for (int i = 0; i < n; i++) {
    	if (r[i] > c[i]) {
    		int d = r[i]-c[i];
    		r[i] -= d;
    		c[i] += d;
    	}
    }

    for (int i = 0; i < n; i++) {
    	s[i] = make_pair(r[i],i);
    }
    sort(s.begin(),s.end());
    for (int i = 0; i < n; i++) {
    	int index = s[i].second;
    	sorted[i] = make_pair(r[index],c[index]);
    }
    return dp(0,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