oj.uz

Submission #399873

# Submission time Handle Problem Language Result Execution time Memory
399873 2021-05-06T19:13:44 Z Jasiekstrz Holiday (IOI14_holiday) C++17
100 / 100
 4844 ms 25592 KB 
#include"holiday.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
multiset<int> not_used,used;
long long curr=0;
void pop_t()
{
	not_used.insert(*used.begin());
	curr-=(*used.begin());
	used.erase(used.begin());
	return;
}
void push_t()
{
	used.insert(*prev(not_used.end()));
	curr+=(*prev(not_used.end()));
	not_used.erase(prev(not_used.end()));
	return;
}
void dc(int dl,int dr,int attraction[],int s,int l,int r,vector<long long> &ans,int c)
{
	if(dl>dr)
		return;
	// solving for mid
	int dmid=(dl+dr)/2;
	while(c*(l-s)+used.size()>dmid)
		pop_t();
	while(c*(l-s)+used.size()<dmid)
		push_t();
	int gg=l;
	ans[dmid]=curr;
	for(int i=l+1;i<r;i++)
	{
		for(int it=1;it<=c && !used.empty();it++)
			pop_t();
		if(!used.empty())
		{
			pop_t();
			not_used.insert(attraction[i]);
			push_t();
			if(curr>ans[dmid])
			{
				ans[dmid]=curr;
				gg=i;
			}
		}
		else
			not_used.insert(attraction[i]);
	}
	// cleaning and recursive calls
	for(int i=r-1;i>l;i--)
	{
		if(not_used.find(attraction[i])!=not_used.end())
			not_used.erase(not_used.find(attraction[i]));
		else
		{
			curr-=attraction[i];
			used.erase(used.find(attraction[i]));
		}
	}
	dc(dl,dmid-1,attraction,s,l,gg+1,ans,c);
	for(int i=l+1;i<=gg;i++)
		not_used.insert(attraction[i]);
	dc(dmid+1,dr,attraction,s,gg,r,ans,c);
	for(int i=gg;i>l;i--)
	{
		if(not_used.find(attraction[i])!=not_used.end())
			not_used.erase(not_used.find(attraction[i]));
		else
		{
			curr-=attraction[i];
			used.erase(used.find(attraction[i]));
		}
	}
	return;
}
long long findMaxAttraction(int n,int start,int d,int attraction[])
{
	vector<long long> ans[2][2];
	for(int i:{0,1})
	{
		for(int j:{0,1})
		{
			ans[i][j].resize(d+10);
			fill(ans[i][j].begin(),ans[i][j].end(),0);
		}
	}
	for(int i=1;i<=d;i++)
		not_used.insert(0);
	for(int rev:{0,1})
	{
		if(start==n-1)
		{
			for(int i=1;i<=d;i++)
				ans[rev][0][i]=ans[rev][1][i]=attraction[n-1];
		}
		else
		{
			not_used.insert(attraction[start]);
			dc(0,d,attraction,start,start,n,ans[rev][0],1);
			dc(0,d,attraction,start,start,n,ans[rev][1],2);
			while(!used.empty())
				pop_t();
			not_used.erase(not_used.find(attraction[start]));
		}
		reverse(attraction,attraction+n);
		start=n-1-start;
		attraction[start]=0;
	}
	long long w=max(ans[0][0][d],ans[1][0][d]);
	for(int i=0;i<=d;i++)
		w=max({w,ans[0][1][i]+ans[1][0][d-i],ans[0][0][i]+ans[1][1][d-i]});
	return w;
}

Compilation message

holiday.cpp: In function 'void dc(int, int, int*, int, int, int, std::vector<long long int>&, int)':
holiday.cpp:28:27: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |  while(c*(l-s)+used.size()>dmid)
      |        ~~~~~~~~~~~~~~~~~~~^~~~~
holiday.cpp:30:27: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |  while(c*(l-s)+used.size()<dmid)
      |        ~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3785 ms 21232 KB Output is correct
2 Correct 4279 ms 21284 KB Output is correct
3 Correct 3774 ms 21384 KB Output is correct
4 Correct 4352 ms 21228 KB Output is correct
5 Correct 4844 ms 15428 KB Output is correct
6 Correct 1939 ms 16200 KB Output is correct
7 Correct 2510 ms 9960 KB Output is correct
8 Correct 2811 ms 10212 KB Output is correct
9 Correct 1705 ms 20032 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 972 KB Output is correct
2 Correct 64 ms 972 KB Output is correct
3 Correct 67 ms 1052 KB Output is correct
4 Correct 66 ms 716 KB Output is correct
5 Correct 60 ms 644 KB Output is correct
6 Correct 15 ms 336 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 12 ms 332 KB Output is correct
9 Correct 12 ms 332 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4030 ms 25588 KB Output is correct
2 Correct 4074 ms 25592 KB Output is correct
3 Correct 869 ms 3088 KB Output is correct
4 Correct 37 ms 480 KB Output is correct
5 Correct 12 ms 332 KB Output is correct
6 Correct 12 ms 368 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 3487 ms 7644 KB Output is correct
9 Correct 3487 ms 7620 KB Output is correct