oj.uz

Submission #115458

# Submission time Handle Problem Language Result Execution time Memory
115458 2019-06-07T15:02:06 Z faustaadp Holiday (IOI14_holiday) C++17
47 / 100
 549 ms 3064 KB 
#include"holiday.h"
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,x,i,j,ki[8080],ka[8080],a[101010],has;
long long int findMaxAttraction(int N, int start, int D, int attraction[]) 
{
	n=N;
	x=start;
	for(i=0;i<n;i++)
		a[i]=attraction[i];
	if(x==0)
	{
		ll hz=0,sz=0;
		priority_queue<ll> pq;
		for(i=0;i<min(n,(ll)D);i++)
		{
			pq.push(-a[i]);
			hz+=a[i];
			sz++;
			while(sz>(D-i))
			{
				sz--;
				hz+=pq.top();
				pq.pop();
			}
			has=max(has,hz);
		}
		return has;
	}
	for(i=x+1;i<n;i++)
	{
		vector<ll> tem;
		for(j=x+1;j<=i;j++)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ka[j+(i-x)+1]=max(ka[j+(i-x)+1],hz);
		}
	}
	for(i=x-1;i>=0;i--)
	{
		vector<ll> tem;
		for(j=x-1;j>=i;j--)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ki[j+(x-i)+1]=max(ki[j+(x-i)+1],hz);
		}
	}
	for(i=1;i<=D;i++)
	{
		ki[i]=max(ki[i-1],ki[i]);
		ka[i]=max(ka[i-1],ka[i]);
	}
	has=max(has,ki[D]);
	has=max(has,ka[D]);
	if(D>1)
		has=max(has,ki[D-1]+a[x]);
	if(D>1)
		has=max(has,ka[D-1]+a[x]);
	for(i=x+1;i<n;i++)
	{
		vector<ll> tem;
		for(j=x+1;j<=i;j++)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ll sisa=D-((i-x)*2+(j+1));
			if(sisa>=0)
				has=max(has,ki[sisa]+hz);
			if(sisa>=1)
				has=max(has,ki[sisa-1]+hz+a[x]);
		}
	}
	for(i=x-1;i>=0;i--)
	{
		vector<ll> tem;
		for(j=x-1;j>=i;j--)
			tem.pb(a[j]);
		sort(tem.begin(),tem.end());
		reverse(tem.begin(),tem.end());
		ll hz=0;
		for(j=0;j<tem.size();j++)
		{
			hz+=tem[j];
			ll sisa=D-((x-i)*2+(j+1));
			if(sisa>=0)
				has=max(has,ka[sisa]+hz);
			if(sisa>=1)
				has=max(has,ka[sisa-1]+hz+a[x]);
		}
	}
	// for(i=0;i<=D;i++)
	// 	cout<<i<<" "<<ki[i]<<"\n";
	// for(i=0;i<=D;i++)
	// 	cout<<i<<" "<<ka[i]<<"\n";
    return has;
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:43:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
holiday.cpp:57:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
holiday.cpp:82:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
holiday.cpp:100:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<tem.size();j++)
           ~^~~~~~~~~~~
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 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2680 KB Output is correct
2 Correct 13 ms 2780 KB Output is correct
3 Correct 14 ms 2800 KB Output is correct
4 Correct 14 ms 2808 KB Output is correct
5 Correct 19 ms 2300 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 11 ms 1660 KB Output is correct
8 Correct 17 ms 1916 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 644 KB Output is correct
2 Correct 136 ms 632 KB Output is correct
3 Correct 133 ms 508 KB Output is correct
4 Correct 271 ms 504 KB Output is correct
5 Correct 226 ms 508 KB Output is correct
6 Correct 41 ms 384 KB Output is correct
7 Correct 28 ms 384 KB Output is correct
8 Correct 26 ms 384 KB Output is correct
9 Correct 26 ms 512 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 141 ms 3064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -