Submission #116429

#	Time	Username	Problem	Language	Result	Execution time	Memory
116429		valentin_imbach	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KiB

aliens

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

using namespace std;

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

vector<int> memo;

long long dp(int a, int 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 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<int>(n);

    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);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:59:5: error: 'sort' was not declared in this scope
     sort(s.begin(),s.end());
     ^~~~
aliens.cpp:59:5: note: suggested alternative: 'qsort'
     sort(s.begin(),s.end());
     ^~~~
     qsort