#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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Correct |
0 ms |
348 KB |
contestant found the optimal answer: 0 == 0 |
4 |
Incorrect |
0 ms |
348 KB |
declared answer doesn't correspond to the split scheme: declared = 1542524, real = 1540057 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
declared answer doesn't correspond to the split scheme: declared = 1093956, real = 914316 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
348 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Incorrect |
1 ms |
604 KB |
declared answer doesn't correspond to the split scheme: declared = 1534210659, real = 1989216017013 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
348 KB |
declared answer doesn't correspond to the split scheme: declared = 21503404, real = 18256972 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
416 ms |
1368 KB |
declared answer doesn't correspond to the split scheme: declared = 1818678304, real = 1718678304 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2009 ms |
9304 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |