이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Z{
vector<ll> vals;
int n;
Z(vector<int> &a){
n = a.size();
vals.resize(n , 0);
vals[0] = a[0];
for(int i = 1;i<n;i++){
vals[i] = vals[i - 1] + a[i];
}
}
ll operator()(int l,int r){
if(l > r)return 0;
assert(n > r);
assert(l <= r);
assert(l >= 0);
int temp = vals[r];
if(l != 0)temp -= vals[l - 1];
return temp;
}
};
signed main(){
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int n, K;cin >> n >> K;
vector<int> a(n);
for(auto &e : a)cin >> e;
Z pref(a);
vector<vector<ll>> dp(n + 1, vector<ll>(K + 1, -1e17));
vector<vector<int>> jump(n + 1, vector<int>(K + 1, -1));
dp[0][0] = 0;
for(int i = 1;i<=n;i++){
dp[i][0] = 0;
for(int j = i;j>=1;j--){
for(int k = 1;k<=K;k++){
ll val =dp[j - 1][k - 1] + pref(j - 1,i - 1)*pref(i, n - 1);
if(val > dp[i][k]){
dp[i][k] = val;
jump[i][k] = j - 1;
}
}
}
}
int MX = -1;
ll val = -1;
for(int i = 0;i<=n;i++){
if(dp[i][K] > val){
val = dp[i][K];
MX = i;
}
}
cout << val << "\n";
vector<int> temp;
int c = K;
while(MX != 0 && MX != -1 && c > 0){
temp.push_back(MX);
MX = jump[MX][c];
--c;
}
reverse(temp.begin(), temp.end());
for(int e : temp)cout << e << " ";
cout << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |