Submission #922670

#	Time	Username	Problem	Language	Result	Execution time	Memory
922670		jpfr12	Split the sequence (APIO14_sequence)	C++17	0 / 100	2009 ms	9304 KiB

sequence

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <string>
#include <map>
#include <math.h>
#include <cmath>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <fstream>
#include <bitset>
#include <iomanip>
 
typedef long long ll;
using namespace std;
int MOD = (int)1e9;
int MAXN = 1e6;
 
//classes

 
 
//global
int n, k;
vector<ll> vec;
vector<vector<ll>> dp;
vector<ll> prefix;
vector<int> parent;

int sol(int left, int temp){
  if(dp[left][temp] != -1) return dp[left][temp];
  if(left == n-1) return 0;
  if(temp == 1){
    ll sum = 0;
    ll best = 0LL;
    for(int i = left; i < n-1; i++){
      sum += vec[i];
      ll mult = sum * (prefix[n-1]-prefix[i]);
      //dp[left][temp] = max(dp[left][temp], mult);
      best = max(best, mult);
      if(best > dp[left][temp]){
        dp[left][temp] = best;
        parent[left] = i+1;
      }
    }
    return dp[left][temp];
  }
  ll sum = 0;
  ll best = 0;
  for(int i = left; i < n-temp; i++){
    sum += vec[i];
    ll mul = sum * (prefix[n-1] - prefix[i]);
    best = max(best, mul + sol(i+1, temp-1));
    //dp[left][temp] = max(dp[left][temp], mul + sol(i+1, temp-1));
    if(best > dp[left][temp]){
      dp[left][temp] = best;
      parent[left] = i+1;
    }
  }
  return dp[left][temp];
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  //ifstream fin("input.txt");
  //ofstream fout("output.txt");
  //stop
  cin >> n >> k;
  vec.resize(n);
  parent.resize(n+1);
  dp.resize(n,vector<ll>(k+1,-1));
  for(ll& i: vec){
    cin >> i;
  }
  prefix.resize(n);
  prefix[0] = vec[0];
  for(int i = 1; i < n; i++){
    prefix[i] = prefix[i-1] + vec[i];
  }
  cout << sol(0, k) << '\n';
  //tests
  /*
  for(int i = 0; i < n; i++){
    for(int j = 0; j <= k; j++){
      cout << dp[i][j] << " ";
    }
    cout << '\n';
  }*/
  int start = parent[0];
  for(int i = 0; i < k; i++){
    cout << start << " ";
    start = parent[start];
  }
  return 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