oj.uz

Submission #29982

# Submission time Handle Problem Language Result Execution time Memory
29982 2017-07-21T11:36:30 Z Bruteforceman Holiday (IOI14_holiday) C++11
24 / 100
 5000 ms 6516 KB 
#include"holiday.h"
#include "bits/stdc++.h"
long long frontR[100010];
long long frontB[100010];
long long backR[100010];
long long backB[100010];
std :: vector <int> P, Q;

long long sortSum(std :: vector <int> &v, int x, int take) {
	if(take < 0) return 0;	
	std :: priority_queue <int, std :: vector <int>, std :: greater <int> > q; 
	long long ans = 0;
	for(int i = 0; i <= x; i++) {
		q.push(v[i]);
		ans += v[i];
		while(q.size() > take) {
			ans -= q.top();
			q.pop();
		}
	}
	return ans;
}
void solveFrontR(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		long long o = sortSum(P, i, m - (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveFrontR(l, m - 1, b, opt);
	solveFrontR(m + 1, r, opt, e);
	frontR[m] = std :: max(frontR[m], best);
}
void solveFrontB(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		long long o = sortSum(P, i, m - 2 * (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveFrontB(l, m - 1, b, opt);
	solveFrontB(m + 1, r, opt, e);
	frontB[m] = std :: max(frontB[m], best);
}
void solveBackR(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		long long o = sortSum(Q, i, m - (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveBackR(l, m - 1, b, opt);
	solveBackR(m + 1, r, opt, e);
	backR[m] = std :: max(backR[m], best);
}
void solveBackB(int l, int r, int b, int e) {
	if(l > r) return ;
	int m = (l + r) >> 1;
	int opt = b;
	long long best = -1;
	for(int i = b; i <= e; i++) {
		long long o = sortSum(Q, i, m - 2 * (i + 1));
		if(o > best) {
			best = o;
			opt = i;
		}
	}
	solveBackB(l, m - 1, b, opt);
	solveBackB(m + 1, r, opt, e);
	backB[m] = std :: max(backB[m], best);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	for(int i = 0; i < start; i++) {
		P.push_back(attraction[i]);
	}
	for(int i = start + 1; i < n; i++) {
		Q.push_back(attraction[i]);
	}
	std :: reverse(P.begin(), P.end());
	if(!P.empty()) {
		solveFrontR(1, d, 0, P.size() - 1);
		solveFrontB(1, d, 0, P.size() - 1);
	}
	if(!Q.empty()) {
		solveBackR(1, d, 0, Q.size() - 1);
		solveBackB(1, d, 0, Q.size() - 1);
	}
	long long ans = 0;
	for(int i = 0; i < d; i++) {
		ans = std :: max(ans, frontB[i] + attraction[start] + backR[d - i - 1]);
		ans = std :: max(ans, frontR[d - i - 1] + attraction[start] + backB[i]);
	}
	for(int i = 0; i <= d; i++) {
		ans = std :: max(ans, frontB[i] + backR[d - i]);
		ans = std :: max(ans, frontR[d - i] + backB[i]);
	}
    return ans;
}

Compilation message

holiday.cpp: In function 'long long int sortSum(std::vector<int>&, int, int)':
holiday.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(q.size() > take) {
                  ^
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5416 KB Output is correct
2 Correct 0 ms 5420 KB Output is correct
3 Correct 0 ms 5416 KB Output is correct
4 Correct 0 ms 5412 KB Output is correct
5 Correct 0 ms 5416 KB Output is correct
6 Correct 0 ms 5412 KB Output is correct
7 Correct 0 ms 5420 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 0 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4696 ms 5412 KB Output is correct
2 Correct 1219 ms 5420 KB Output is correct
3 Correct 3496 ms 5416 KB Output is correct
4 Correct 1873 ms 5412 KB Output is correct
5 Correct 1573 ms 5412 KB Output is correct
6 Correct 159 ms 5416 KB Output is correct
7 Correct 46 ms 5416 KB Output is correct
8 Correct 66 ms 5412 KB Output is correct
9 Correct 63 ms 5420 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 6516 KB Execution timed out
2 Halted 0 ms 0 KB -