Submission #298028

#	Time	Username	Problem	Language	Result	Execution time	Memory
298028		Plurm	Holiday (IOI14_holiday)	C++11	24 / 100	5078 ms	2028 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int* attraction;
int start;
int n,d;
long long computeManyMax(int k, int l, int r){
	vector<int> v;
	for(int i = l; i <= r; i++) v.push_back(attraction[i]);
	sort(v.begin(), v.end(), greater<int>());
	long long ans = 0;
	for(int i = 0; i < k && i < v.size(); i++) ans += 1ll * v[i];
	return ans;
}
long long divideConquer(int l, int r, int ll, int rr){
	if(l > r) return 0ll;
	int m = (l+r)/2;
	long long ans = 0;
	int rmidx = -1;
	int lmidx = -1;
	for(int i = ll; i <= rr; i++){
		int dist = m-i+min(start-i,m-start);
		if(dist > d) continue;
		long long cur = computeManyMax(d - dist, i, m);
		if(cur > ans){
			ans = cur;
			lmidx = rmidx = i;
		}else if(cur == ans){
			rmidx = i;
		}
	}
	ans = max(ans, divideConquer(l, m-1, ll, rmidx));
	ans = max(ans, divideConquer(m+1, r, lmidx, rr));
	return ans;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	::attraction = attraction;
	::start = start;
	::n = n;
	::d = d;
	return divideConquer(start, n-1, 0, start);
}

Compilation message (stderr)

holiday.cpp: In function 'long long int computeManyMax(int, int, int)':
holiday.cpp:12:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < k && i < v.size(); i++) ans += 1ll * v[i];
      |                          ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53