oj.uz

Submission #29908

# Submission time Handle Problem Language Result Execution time Memory
29908 2017-07-21T10:24:19 Z Bruteforceman Holiday (IOI14_holiday) C++11
24 / 100
 5000 ms 6272 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;

void frontCal(int d) {
	frontB[d] = frontR[d] = 0;

	std :: priority_queue <int, std :: vector <int>, std :: greater <int> > q;
	int take = 0;
	long long ans = 0;
	
	for(size_t i = 0; i < P.size(); i++) {
		++take;
		if(take > d) break;
		q.push(P[i]);
		ans += P[i];
		while(q.size() + take > d) {
			ans -= q.top();
			q.pop();
		}
		frontR[d] = std :: max(frontR[d], ans);
	}
	
	take = 0;
	ans = 0;
	while(!q.empty()) q.pop();
	for(size_t i = 0; i < P.size(); i++) {
		take += 2;
		if(take > d) break;
		q.push(P[i]);
		ans += P[i];
		while(q.size() + take > d) {
			ans -= q.top();
			q.pop();
		} 
		frontB[d] = std :: max(frontB[d], ans);
	}
}
void backCal(int d) {
	backB[d] = backR[d] = 0;
	
	std :: priority_queue <int, std :: vector <int>, std :: greater <int> > q;
	int take = 0;
	long long ans = 0;
	
	for(size_t i = 0; i < Q.size(); i++) {
		++take;
		if(take > d) break;
		q.push(Q[i]);
		ans += Q[i];
		
		while(q.size() + take > d) {
			ans -= q.top();
			q.pop();
		}
		backR[d] = std :: max(backR[d], ans);
	}
	
	take = 0;
	ans = 0;
	while(!q.empty()) q.pop();
	for(size_t i = 0; i < Q.size(); i++) {
		take += 2;
		if(take > d) break;
		
		q.push(Q[i]);
		ans += Q[i];
		
		while(q.size() + take > d) {
			ans -= q.top();
			q.pop();
		}
		backB[d] = std :: max(backB[d], ans);
	}
}

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());
	
	for(size_t i = 0; i <= d; i++) {
		frontCal(i);
		backCal(i);
	} 	
	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 'void frontCal(int)':
holiday.cpp:21:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(q.size() + take > d) {
                         ^
holiday.cpp:36:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(q.size() + take > d) {
                         ^
holiday.cpp: In function 'void backCal(int)':
holiday.cpp:56:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(q.size() + take > d) {
                         ^
holiday.cpp:73:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(q.size() + take > d) {
                         ^
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(size_t i = 0; i <= d; i++) {
                      ^
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 5416 KB Output is correct
3 Correct 0 ms 5420 KB Output is correct
4 Correct 0 ms 5416 KB Output is correct
5 Correct 0 ms 5412 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 6272 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3223 ms 5412 KB Output is correct
2 Correct 739 ms 5416 KB Output is correct
3 Correct 2596 ms 5416 KB Output is correct
4 Correct 1176 ms 5416 KB Output is correct
5 Correct 1022 ms 5412 KB Output is correct
6 Correct 56 ms 5420 KB Output is correct
7 Correct 26 ms 5412 KB Output is correct
8 Correct 26 ms 5420 KB Output is correct
9 Correct 26 ms 5416 KB Output is correct

Subtask #4
0 / 53.0

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