oj.uz

Submission #15840

# Submission time Handle Problem Language Result Execution time Memory
15840 2015-07-30T15:42:35 Z myungwoo Holiday (IOI14_holiday) C++14
24 / 100
 5000 ms 3156 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
typedef long long lld;

static int N, S, T;
static int A[MAXN];

lld proc()
{
	lld ret = 0;
	for (int i=S;i;i--){
		priority_queue <int> que;
		lld sum = 0;
		int left = T;
		for (int j=S;j>=i;j--){
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
			sum += A[j];
			ret = max(ret, sum);
			que.push(-A[j]);
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
		}
		while (left < S-i){
			if (que.empty()) break;
			sum += que.top(); que.pop();
			left++;
		}
		if (left < S-i) break;
		left -= S-i;
		for (int j=S+1;j<=N;j++){
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
			sum += A[j];
			ret = max(ret, sum);
			que.push(-A[j]);
			if (!left){
				if (que.empty()) break;
				sum += que.top(); que.pop();
				left++;
			}
			left--;
		}
	}
	return ret;
}

lld findMaxAttraction(int n, int start, int d, int arr[])
{
	N = n, S = start+1, T = d;
	for (int i=1;i<=N;i++) A[i] = arr[i-1];
	lld ret = proc();
	if (!S) return ret;
	reverse(A+1, A+N+1); S = N-S+1;
	return max(ret, proc());
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2376 KB Output is correct
2 Correct 0 ms 2376 KB Output is correct
3 Correct 0 ms 2380 KB Output is correct
4 Correct 0 ms 2376 KB Output is correct
5 Correct 0 ms 2376 KB Output is correct

Subtask #2
0.0 / 23.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 2384 KB Output is correct
2 Correct 63 ms 2380 KB Output is correct
3 Correct 184 ms 2376 KB Output is correct
4 Correct 300 ms 2376 KB Output is correct
5 Correct 217 ms 2380 KB Output is correct
6 Correct 7 ms 2380 KB Output is correct
7 Correct 7 ms 2384 KB Output is correct
8 Correct 13 ms 2376 KB Output is correct
9 Correct 13 ms 2376 KB Output is correct

Subtask #4
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 4884 ms 0 KB SIGKILL Killed
2 Halted 0 ms 0 KB -