이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ff first
#define ss second
using namespace std;
const int N=1e4+7, M=1e9+7;
ll a[N], dp[N][206], res[N][206], pref[N];
void solve()
{
int n, k;
cin >> n >> k;
for (int i=1;i<=n;i++) cin >> a[i];
for (int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i];
for (int i=0;i<=n;i++){
for (int j=i+1;j<=n;j++){
for (int q=1;q<=k;q++){
if (dp[j][q] <= dp[i][q-1]+(pref[j]-pref[i])*(pref[n]-pref[j])){
dp[j][q] = dp[i][q-1]+(pref[j]-pref[i])*(pref[n]-pref[j]);
res[j][q]=i+1;
}
}
}
}
ll ress=0, mx=0;
for (int i=1;i<=n;i++){
if (mx < dp[i][k]) mx=dp[i][k], ress=i;
}
ll jv=res[ress][k];
vector <ll> ans;
while (k > 0){
ans.push_back(res[jv][k]);
jv=res[jv][k];
k--;
}
reverse(ans.begin(), ans.end());
cout << mx <<"\n";
for (auto l:ans) cout << l <<" ";
return ;
}
int main()
{
ios;
int t=1;
// cin >> t;
while (t--){
solve();
cout <<"\n";
}
return 0;
}
# | 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... |