Submission #223275

#	Time	Username	Problem	Language	Result	Execution time	Memory
223275		cgiosy	Split the sequence (APIO14_sequence)	C++17	0 / 100	20 ms	768 KiB

sequence

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N=1e5+5;
int n,k,a[N],p[N],t1,q[N],t2;
int check(ll mid){
	ll sum=0;int res=0;
	for(int i=1;i<=n;++i){
		sum+=a[i];
		if(sum>=mid)++res,sum=0;
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&k); ++k;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	ll l=0,r=5e9,res;
	while(l<=r){
		ll mid=l+r>>1;
		if(check(mid)>=k)res=mid,l=mid+1;
		else r=mid-1;
	}
	ll sum=0;
	for(int i=1;i<=n;++i){
		sum+=a[i];
		if(sum>=res)p[++t1]=i,sum=0;
	}
	sum=0;
	for(int i=n;i;--i){
		sum+=a[i];
		if(sum>=res+1)q[++t2]=i,sum=0;
	}
	if(t1!=k||p[t1]!=n) for(int i=1;i<=t1;++i) if(p[i]+1==q[k-i]){
		for(int j=k-i-1;j;--j)p[++i]=q[j]-1;
		break;
	}
	ll x=0;
	for(int i=1; i<=n; i++) a[i]+=a[i-1];
	for(int i=1; i<=k; i++) x+=1LL*(a[p[i]]-a[p[i-1]])*a[p[i-1]];
	printf("%lld\n", x);
	for(int i=1; i<k; i++) printf("%d ", p[i]);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=l+r>>1;
          ~^~
sequence.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k); ++k;
  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:17:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;++i)scanf("%d",&a[i]);
                       ~~~~~^~~~~~~~~~~~
sequence.cpp:27:3: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(sum>=res)p[++t1]=i,sum=0;
   ^~

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