oj.uz

Submission #15709

# Submission time Handle Problem Language Result Execution time Memory
15709 2015-07-16T02:53:10 Z gs14004 Holiday (IOI14_holiday) C++14
47 / 100
 5000 ms 2248 KB 
#include"holiday.h"
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long lint;
priority_queue<int, vector<int>, greater<int> > pq;

lint ret;
int *a, st, dist;

void divConq(int s, int e, int rs, int re){ // boilerplate
	if(s > e) return;
	int m = (s+e)/2;
	lint copt = 0, cres = -1;
	int opt = 0;
	for(int i=m; i<rs; i++){
		pq.push(a[i]);
		copt += a[i];
	}
	for(int i=rs; i<=re; i++){
		pq.push(a[i]);
		copt += a[i];
	    while(!pq.empty() && (int)pq.size() > dist - (i - m + min(i - st, st - m) )){
            copt -= pq.top();
            pq.pop();
        }
        if(cres < copt){
        	cres = copt;
        	opt = i;
        }
	}
	ret = max(ret, cres);
	while(!pq.empty()) pq.pop();
	divConq(s,m-1,rs,opt);
	divConq(m+1,e,opt,re);
} 

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	a = attraction;
	st = start;
	dist = d;
	divConq(0, start, start, n-1);
	return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1480 KB Output is correct
2 Correct 0 ms 1472 KB Output is correct
3 Correct 0 ms 1476 KB Output is correct
4 Correct 0 ms 1472 KB Output is correct
5 Correct 0 ms 1472 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2248 KB Output is correct
2 Correct 17 ms 2244 KB Output is correct
3 Correct 16 ms 2248 KB Output is correct
4 Correct 16 ms 2244 KB Output is correct
5 Correct 25 ms 1864 KB Output is correct
6 Correct 8 ms 1604 KB Output is correct
7 Correct 13 ms 1864 KB Output is correct
8 Correct 17 ms 1860 KB Output is correct
9 Correct 5 ms 1608 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 1480 KB Output is correct
2 Correct 253 ms 1472 KB Output is correct
3 Correct 306 ms 1476 KB Output is correct
4 Correct 128 ms 1476 KB Output is correct
5 Correct 248 ms 1476 KB Output is correct
6 Correct 2 ms 1472 KB Output is correct
7 Correct 5 ms 1476 KB Output is correct
8 Correct 9 ms 1476 KB Output is correct
9 Correct 15 ms 1476 KB Output is correct

Subtask #4
0.0 / 53.0

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