oj.uz

Submission #136107

# Submission time Handle Problem Language Result Execution time Memory
136107 2019-07-24T17:55:15 Z arthurconmy Holiday (IOI14_holiday) C++14
24 / 100
 5000 ms 2152 KB 
#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "holiday.h"
#endif
using namespace std;
using ll=long long;

ll findMaxAttraction(int n, int sta, int d, int A[])
{
	ll global_ans=0LL;

	for(int r=sta; r<n; r++)
	{
		ll ans=0LL;

		priority_queue<ll> active;
		ll active_sum=0LL;

		for(int i=sta+1; i<=r; i++)
		{
			active_sum += ll(A[i]);
			active.push(ll(-A[i]));
		}

		for(int i=sta; i>=0; i--)
		{
			active.push(ll(-A[i]));
			active_sum += ll(A[i]);

			// cout << 2*(r-sta) + sta-i << endl;

			while(int(active.size()) + 2*(r-sta) + sta-i > d && !active.empty())
			{
				active_sum += active.top();
				active.pop();
			}

			if(int(active.size()) + 2*(r-sta) + sta-i <= d) ans = max(ans,active_sum);
		}

		global_ans = max(global_ans,ans);

		// cout << r << " " << ans << endl;
	}

	// reverse that shit afterwards

	int B[n];

	for(int i=0; i<n; i++) B[i]=A[n-i-1];
	sta = n-sta-1;

	for(int r=sta; r<n; r++)
	{
		ll ans=0LL;

		priority_queue<ll> active;
		ll active_sum=0LL;

		for(int i=sta+1; i<=r; i++)
		{
			active_sum += ll(B[i]);
			active.push(ll(-B[i]));
		}

		for(int i=sta; i>=0; i--)
		{
			active.push(ll(-B[i]));
			active_sum += ll(B[i]);

			// cout << 2*(r-sta) + sta-i << endl;

			while(int(active.size()) + 2*(r-sta) + sta-i > d && !active.empty())
			{
				active_sum += active.top();
				active.pop();
			}

			if(int(active.size()) + 2*(r-sta) + sta-i <= d) ans = max(ans,active_sum);
		}

		global_ans = max(global_ans,ans);

		// cout << r << " " << ans << endl;
	}

	return global_ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5008 ms 1500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 376 KB Output is correct
2 Correct 40 ms 480 KB Output is correct
3 Correct 127 ms 488 KB Output is correct
4 Correct 386 ms 504 KB Output is correct
5 Correct 279 ms 376 KB Output is correct
6 Correct 34 ms 376 KB Output is correct
7 Correct 35 ms 380 KB Output is correct
8 Correct 34 ms 376 KB Output is correct
9 Correct 33 ms 376 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5017 ms 2152 KB Time limit exceeded
2 Halted 0 ms 0 KB -