Submission #100215

#	Time	Username	Problem	Language	Result	Execution time	Memory
100215		TadijaSebez	Split the sequence (APIO14_sequence)	C++11	100 / 100	419 ms	82956 KiB

sequence

	#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<ctime>
    #define maxn 210
    #define maxm 100010
    using namespace std;
    typedef long long LL;
    bool awal=true;
    struct Node
    {
    	LL S,G;
    	int id;
    	Node() {}
    	Node(LL S,LL G,int id): S(S),G(G),id(id) {}
    };
    int pre[maxn][maxm],a[maxm],n,m;
    LL sum[maxm],dp[maxm];
    void read()
    {
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;++i)
    	{
    		scanf("%d",a+i);
    		sum[i]=sum[i-1]+a[i];
    	}
    }
    void print(int n,int m)
    {
    	if(n==0) return;
    	print(n-1,pre[n][m]);
    	if(awal==true) { awal=false; printf("%d",pre[n][m]); }
    	else printf(" %d", pre[n][m]);
    }
    void Dp()
    {
    	static Node queue[maxm];
    	for(int i=1;i<=m;++i)
    	{
    		int front=1,rear=1;
    		queue[rear]=Node(dp[i]-sum[i]*sum[i],sum[i],i);
    		for(int j=i+1;j<=n;++j)
    		{
    			while(front<rear&&queue[front].S+sum[j]*queue[front].G<=queue[front+1].S+sum[j]*queue[front+1].G)
    				++front;
    			Node now(dp[j]-sum[j]*sum[j],sum[j],j);
    			dp[j]=queue[front].S+sum[j]*queue[front].G;
    			pre[i][j]=queue[front].id;
    			while(front<rear&&(now.S-queue[rear].S)*(queue[rear].G-queue[rear-1].G)>=(queue[rear].S-queue[rear-1].S)*(now.G-queue[rear].G))
    				--rear;
    			queue[++rear]=now;
    		}
    	}
    	cout<<dp[n]<<endl;
    	print(m,n);
    }
    int main()
    {
    	//freopen("sequence.in","r",stdin);
    	//freopen("sequence.out","w",stdout);
    	read();
    	Dp();
    	printf("\n");
    	//system("pause");
    	return 0;
    }

Compilation message (stderr)

sequence.cpp: In function 'void read()':
sequence.cpp:24:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d%d",&n,&m);
      ~~~~~^~~~~~~~~~~~~~
sequence.cpp:27:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",a+i);
       ~~~~~^~~~~~~~~~

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