Submission #562489

#	Time	Username	Problem	Language	Result	Execution time	Memory
562489		gs15120	Split the sequence (APIO14_sequence)	C++14	100 / 100	1248 ms	83100 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define pi 3.1415926535897932384626
using namespace std;
struct P{
  int x,y,z;
  bool operator <(const P &a)const
  {
    //if(x!=a.x)
    return x<a.x;
   // return z<a.z;
  };
 
};

int dx[10]={1,0,-1,0,1,1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,-1};
const ll mod=1000000007,Max=mod,Min=-Max;
int a,b;
int o[111111],c[222][111111];
ll dp[111111],ss[111111],aa[111111];

void f(int p,int n,int m,int x,int y)
{
  if(n>m) return;
  int h=(n+m)/2;
  aa[h]=dp[h+1]+(ss[a]-ss[h])*o[h];
  c[p][h]=h;
  for(int i=max(x,h);i<=y;i++)
  if(aa[h]<(ss[a]-ss[i])*(ss[i]-ss[h-1])+dp[i+1])
  {
    aa[h]=(ss[a]-ss[i])*(ss[i]-ss[h-1])+dp[i+1];
    c[p][h]=i;
  }
  f(p,n,h-1,x,c[p][h]);
  f(p,h+1,m,c[p][h],y);
}


int main()
{
  scanf("%d %d",&a,&b);
  for(int t=1;t<=a;t++)
  {
    scanf("%d",&o[t]);
    ss[t]=ss[t-1]+o[t];
  }
  for(int t=1;t<=a;t++) c[0][t]=a;
  for(int i=1;i<=b;i++)
  {
    aa[111111];
    memset(aa,-1,sizeof(aa));
    f(i,1,a,1,a);
    
    
    for(int t=1;t<=a;t++)
      dp[t]=aa[t];
  }
  printf("%lld\n",dp[1]);
  int e=1;
  for(int t=b;t;t--)
  {
    //printf("%d %d\n",c[t][e],e);
    printf("%d ",c[t][e]);
    e=c[t][e]+1;
  }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:51:14: warning: statement has no effect [-Wunused-value]
   51 |     aa[111111];
      |     ~~~~~~~~~^
sequence.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d %d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d",&o[t]);
      |     ~~~~~^~~~~~~~~~~~

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