Submission #225980

#	Time	Username	Problem	Language	Result	Execution time	Memory
225980		bharat2002	Split the sequence (APIO14_sequence)	C++14	0 / 100	33 ms	2432 KiB

sequence

/*input

*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
queue<int> ans;set<int> inds;int arr[N], pref[N];
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, k;cin>>n>>k;pref[0]=0;
	for(int i=1;i<=n;i++) {cin>>arr[i];pref[i]=pref[i-1] + arr[i];}
	int st=0, fin=n;int mval=0;int pos;
	for(int i=1;i<=n;i++)
	{
		if(mval<pref[i]*(pref[n]-pref[i]))
		{
			mval=pref[i]*(pref[n]-pref[i]);pos=i;
		}
	}
	inds.insert(pos);ans.push(pos);set<int>::iterator it=inds.begin();
	int pval=mval;inds.insert(n);
	for(int i=2;i<=k;i++)
	{
		it=inds.begin();st=0;
		mval=0;
		while(it!=inds.end())
		{
			for(int j=st+1;j<=(*it);j++)
			{
				int tv=(pref[j]-pref[st])*(pref[(*it)]-pref[j]);
				if(tv>mval){
					mval=tv;pos=j;
				}
			}
			st=(*it);it++;
		}
		inds.insert(pos);ans.push(pos);
		pval+=mval;
	}
	cout<<pval<<endl;
	while(!ans.empty()) {cout<<ans.front()<<" ";ans.pop();}
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:23:12: warning: unused variable 'fin' [-Wunused-variable]
  int st=0, fin=n;int mval=0;int pos;
            ^~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29