Submission #106918

#	Time	Username	Problem	Language	Result	Execution time	Memory
106918		nxteru	Split the sequence (APIO14_sequence)	C++14	100 / 100	542 ms	83704 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000000000000
struct t{
	ll x,y,q;
};
bool check(t a,t b,t c){
	return (c.y-b.y)*(a.x-b.x)<=(b.y-a.y)*(b.x-c.x);
}
int n,m,b[205][100005],l,r;
ll dp[2][100005],s[100005];
t dq[100005];
vector<int>ans;
int main(void){
	scanf("%d%d",&n,&m);
	m++;
	for(int i=1;i<=n;i++){
		ll a;
		scanf("%d",&a);
		s[i]=s[i-1]+a;
	}
	for(int j=0;j<=n;j++)dp[0][j]=INF;
	dp[0][0]=0;
	for(int i=1;i<=m;i++){
		l=0,r=0;
		int o=(i-1)%2,p=i%2;
		for(int j=0;j<=n;j++)dp[p][j]=INF;
		for(int j=1;j<=n;j++){
			if(dp[o][j-1]<INF){
				t p=t{-2LL*s[j-1],s[j-1]*s[j-1]+dp[o][j-1],j-1};
				while(r-2>=l&&check(dq[r-2],dq[r-1],p))r--;
				dq[r++]=p;
				while(l+1<r&&dq[l].x*s[j]+dq[l].y>=dq[l+1].x*s[j]+dq[l+1].y)l++;
			}
			if(l<r){
				b[i][j]=dq[l].q;
				dp[p][j]=dq[l].x*s[j]+dq[l].y+s[j]*s[j];
			}
		}
	}
	printf("%lld\n",(s[n]*s[n]-dp[m%2][n])/2LL);
	int x=n;
	for(int i=m;i>1;i--){
		ans.PB(b[i][x]);
		x=b[i][x];
	}
	for(int i=ans.size()-1;i>=0;i--){
		printf("%d",ans[i]);
		if(i==0)printf("\n");
		else printf(" ");
	}
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:26:16: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
   scanf("%d",&a);
              ~~^
sequence.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a);
   ~~~~~^~~~~~~~~

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