Submission #74721

#	Time	Username	Problem	Language	Result	Execution time	Memory
74721		goodbaton	Split the sequence (APIO14_sequence)	C++14	78 / 100	635 ms	83596 KiB

sequence

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 101000

int n,m;
int a[SIZE];
ll sum[SIZE];
ll dp[2][SIZE];
int dp_back[201][SIZE];
int deq[SIZE];

ll f_a(int t){
  return sum[t];
}

ll f_b(int k, int t){
  return - sum[n]*sum[t] + dp[k][t];
}

ll f(int k, int t, int x){
  return f_a(t) * sum[x] + f_b(k,t);
}

bool check(int k,int f1, int f2, int f3){
  ll a = (f_a(f2)-f_a(f1)) * (f_b(k,f3)-f_b(k,f2));
  ll b = (f_b(k,f2)-f_b(k,f1)) * (f_a(f3)-f_a(f2));
  return  a >= b;
}

int main(){
  
  scanf("%d%d",&n,&m);
  
  sum[0] = a[0] = 0;
  
  for(int i=1;i<=n;i++){
    scanf("%d",a+i);
    sum[i] = sum[i-1] + a[i];
  }

  dp[0][0] = 0;
  
  for(int i=0;i<m;i++){
    int s=0, t=1;
    deq[0] = 0;
  
    for(int j=1;j<=n;j++){
      while(s+1 < t && f(i%2,deq[s],j) < f(i%2,deq[s+1],j)) s++;
      dp[1-i%2][j] = sum[n]*sum[j] - sum[j]*sum[j] + f(i%2,deq[s],j);
      dp_back[i+1][j] = deq[s];

      while(s+1 < t && check(i%2,deq[t-2], deq[t-1], j)) t--;
      deq[t++] = j;
    }
  }

  ll ans = 0;
  int p = 0;
  
  for(int i=0;i<=n;i++){
    if(ans <= dp[m%2][i]){
      p = i;
      ans = dp[m%2][i];
    }
  }

  vector<int> vec;
  vec.push_back(p);
  
  for(int i=m;i>1;i--){
    p = dp_back[i][p];
    vec.push_back(p);
  }

  
  /*
  for(int i=0;i<=m;i++){
    for(int j=0;j<=n;j++){
      cerr << i << " " << j << " : " << dp[i][j] << endl;
    }
  }
  */  
  
  printf("%lld\n",ans);

  for(int i=vec.size()-1;i>=0;i--){
    printf("%d%c",vec[i]," \n"[i==0]);
  }
  
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
   ~~~~~^~~~~~~~~~~~~~
sequence.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",a+i);
     ~~~~~^~~~~~~~~~

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