Submission #784318

#	Time	Username	Problem	Language	Result	Execution time	Memory
784318		Lyrically	Holiday (IOI14_holiday)	C++17	0 / 100	1756 ms	13408 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%d",&x);return x;}
void print(int x){printf("%d\n",x);}
void file(string s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const int mod=998244353;
int a[100005];
int n,s,d;
long long calc(int x)
{
	multiset<int> st;
	for(int i=x;i<=s;i++){st.insert(a[i]);}
	//i<=2*s-x
	long long res=0;
	long long cur=0;
	for(int i=s;i-s<=s-x;i++)
	{
		int go=2*i-s-x;
		if(go>d){break;}
		go=d-go;
		if(i==s)
		{
			vector<int> v;
			for(int j=1;j<=go;j++)
			{
				if(st.empty()){break;}
				v.pb(*(--st.end()));cur+=*(--st.end());
				st.erase(--st.end());
			}
			res=cur;st.clear();
			for(auto p:v){st.insert(p);}
		}
		else
		{
			st.insert(a[i]);cur+=a[i];cur-=*(st.begin());
			st.erase(st.begin());
			if(!st.empty())
			{
				cur-=*st.begin();st.erase(st.begin());
			}
			res=max(res,cur);
		}//print(go);
	}
	//print(res);cout<<2*s-x+1<<endl;
	st.clear();
	for(int i=x;i<=2*s-x+1;i++){st.insert(a[i]);}
	cur=0;
	for(int i=2*s-x+1;i<=n;i++)
	{
		int go=i+s-2*x;
		if(go>d){break;}
		go=d-go;
		if(i==2*s-x+1)
		{
			vector<int> v;
			for(int j=1;j<=go;j++)
			{
				if(st.empty()){break;}
				v.pb(*(--st.end()));cur+=*(--st.end());
				st.erase(--st.end());
			}
			res=cur;st.clear();
			for(auto p:v){st.insert(p);}
		}
		else
		{
			st.insert(a[i]);cur+=a[i];cur-=*(st.begin());
			st.erase(st.begin());
			res=max(res,cur);
		}
	}
	//print(res);
	return res;
}
long long findMaxAttraction(int N,int S,int D,int attr[])
{
	n=N,s=S+1,d=D;
	rep(i,n){a[i+1]=attr[i];}
	//往左去到的最远地方
	long long res=0;
	for(int i=1;i<=s;i++)
	{
		res=max(res,calc(i));
	}
	reverse(a+1,a+n+1);
	if(s!=1)
	{
		s=n-s+1;
		for(int i=1;i<=s;i++)
		{
			//if(calc(i)==62){print(i);}
			res=max(res,calc(i));
		}
	}
	return res;
}

Compilation message (stderr)

holiday.cpp: In function 'int read()':
holiday.cpp:7:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | int read(){int x;scanf("%d",&x);return x;}
      |                  ~~~~~^~~~~~~~~
holiday.cpp: In function 'void file(std::string)':
holiday.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53