Submission #389967

#	Time	Username	Problem	Language	Result	Execution time	Memory
389967		ahmet	Split the sequence (APIO14_sequence)	C++14	0 / 100	17 ms	3652 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define zaman cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))	
#define endl '\n'
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
const int mx=2e5+6;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,k;cin >> n >> k;
	vector <int> a(n+1,0),p(n+1,0);
	ref(i,1,n)cin >> a[i];
	ref(i,1,n){
		p[i]=a[i]+p[i-1];
	}
	int say=0;
	bitset <mx> b;ll ans=0,sum=0,top=0;b[n]=1;
	while(say<k){
		sum=0;top=0;
		vector <int> at;int son=1;
		priority_queue <pair<int,int> > pq;
		for(int i=1;i<=n;++i){
			sum+=a[i];top=0;
			at.pb(a[i]);
			if(b[i]){
				for(int j=son;j<=i;++j){
					top+=at[j-son];
					pq.push(mp(top*(sum-top),j));
				}
				sum=0;
				son=i+1;
				continue;
			}
		}
		ans+=pq.top().first;
		b[pq.top().second]=1;
		//cout << pq.top().second << " " << pq.top().first << endl;
		++say;
	}
	cout << ans<<endl;
	rep(i,n){
		if(b[i])cout<<i<<" ";
	}

}	
	

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:5:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
      |                                   ^
sequence.cpp:17:2: note: in expansion of macro 'ref'
   17 |  ref(i,1,n)cin >> a[i];
      |  ^~~
sequence.cpp:5:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
      |                                   ^
sequence.cpp:18:2: note: in expansion of macro 'ref'
   18 |  ref(i,1,n){
      |  ^~~
sequence.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
      |                                ^
sequence.cpp:46:2: note: in expansion of macro 'rep'
   46 |  rep(i,n){
      |  ^~~

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