이 제출은 이전 버전의 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<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(K + 2)));
vector<vector<vector<int>>> spp(n, vector<vector<int>>(n, vector<int>(K + 2)));
vector<vector<vector<int>>> spk(n, vector<vector<int>>(n, vector<int>(K + 2)));
vector<int> a(n);
for(auto &e : a)cin >> e;
Z pref(a);
auto solve = [&](auto &self, int l,int r,int k)->ll{
if(l > r)return 0;
if(k == 0)return 0;
if(dp[l][r][k] != 0)return dp[l][r][k];
assert(k > 0);
ll ans = 0;
for(int i = l;i<r;i++){
// (l, i), (l + 1, r)
for(int sk = 0;sk<k;sk++){
ll val = pref(l, i)*pref(i + 1, r) + self(self, l, i, sk) + self(self, i + 1, r, k - sk - 1);
if(val > ans){
spp[l][r][k] = i;
spk[l][r][k] = sk;
ans = val;
}
}
}
return (dp[l][r][k] = ans);
};
vector<int> A;
auto get = [&](auto &self,int l,int r,int k)->void{
if(l > r)return;
if(k == 0)return;
A.push_back(spp[l][r][k]);
int i = spp[l][r][k], sk = spk[l][r][k];
self(self, l, i, sk);
self(self, i + 1, r, k - sk - 1);
};
cout << solve(solve, 0, n - 1, K) << "\n";
get(get, 0, n - 1, K);
for(auto e : A)cout << e + 1 << " ";
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... |