Submission #922672

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
922672	2024-02-05T23:20:22 Z	jpfr12	Split the sequence (APIO14_sequence)	C++17	0 / 100	2000 ms	9304 KB

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 = -1;
    for(int i = left; i < n; 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 = -1;
  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.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	contestant found the optimal answer: 108 == 108
2	Correct	344 KB	contestant found the optimal answer: 999 == 999
3	Correct	344 KB	contestant found the optimal answer: 0 == 0
4	Incorrect	348 KB	declared answer doesn't correspond to the split scheme: declared = 1542524, real = 1540057
5	Halted	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	declared answer doesn't correspond to the split scheme: declared = 1093956, real = 914316
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	0 ms	348 KB	contestant found the optimal answer: 311760000 == 311760000
3	Incorrect	0 ms	604 KB	Integer 0 violates the range [1, 199]
4	Halted	0 ms	0 KB	-