#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int, int>
const int sz = 1e4 + 5;
long long a[sz], s[sz];
int n, k;
int f[1005][205], pre[1005][205];
namespace SUB123{
bool ok(){
return (n <= 200);
}
void solve(){
// vector<vector<int>> f(n+5, vector<int>(k+5, 0));
// vector<vector<int>> pre(n+5, vector<int>(k+5, -1));
memset(pre, -1, sizeof pre);
for(int j=1; j<=k; ++j){
for(int i=1; i<=n; ++i){
int L = 0, R = s[n] - s[i];
for(int g=i; g>=j; --g){
L += a[g];
if(f[g-1][j-1] + (L * R) > f[i][j]){
f[i][j] = f[g-1][j-1] + (L * R);
pre[i][j] = g-1;
}
}
}
}
// for(int i=1; i<=n; ++i){
// for(int j=1; j<=k; ++j){
// cout<<f[i][j]<<' ';
// }
// cout<<endl;
// }
int ma = 0, p = -1;
for(int i=n; i>=1; --i){
if(f[i][k] > ma){
ma = f[i][k];
p = i;
}
}
vector<int> v;
int x = p;
while(x != -1){
v.push_back(x);
x = pre[x][k--];
}
v.pop_back();
cout<<ma<<endl;
while(v.size()){
cout<<v.back()<<' ';
v.pop_back();
}
//---------------------
exit(0);
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("main.inp","r",stdin);
//freopen("main.out","w",stdout);
cin>>n>>k;
for(int i=1; i<=n; ++i){
cin>>a[i];
s[i] = s[i-1] + a[i];
}
SUB123::solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2648 KB |
contestant found the optimal answer: 108 == 108 |
2 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 999 == 999 |
3 |
Runtime error |
3 ms |
5076 KB |
Execution killed with signal 11 |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 1093956 == 1093956 |
2 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 302460000 == 302460000 |
3 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 122453454361 == 122453454361 |
4 |
Correct |
1 ms |
2660 KB |
contestant found the optimal answer: 93663683509 == 93663683509 |
5 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 1005304678 == 1005304678 |
6 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 933702 == 933702 |
7 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 25082842857 == 25082842857 |
8 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 687136 == 687136 |
9 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 27295930079 == 27295930079 |
10 |
Correct |
1 ms |
2648 KB |
contestant found the optimal answer: 29000419931 == 29000419931 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 610590000 == 610590000 |
2 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 311760000 == 311760000 |
3 |
Correct |
3 ms |
2652 KB |
contestant found the optimal answer: 1989216017013 == 1989216017013 |
4 |
Correct |
1 ms |
2652 KB |
contestant found the optimal answer: 1499437552673 == 1499437552673 |
5 |
Correct |
2 ms |
2652 KB |
contestant found the optimal answer: 1019625819 == 1019625819 |
6 |
Incorrect |
3 ms |
2652 KB |
Integer 200 violates the range [1, 199] |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
3676 KB |
contestant found the optimal answer: 21503404 == 21503404 |
2 |
Correct |
3 ms |
3532 KB |
contestant found the optimal answer: 140412195 == 140412195 |
3 |
Correct |
80 ms |
3692 KB |
contestant found the optimal answer: 49729674225461 == 49729674225461 |
4 |
Correct |
3 ms |
3672 KB |
contestant found the optimal answer: 37485571387523 == 37485571387523 |
5 |
Correct |
86 ms |
3676 KB |
contestant found the optimal answer: 679388326 == 679388326 |
6 |
Correct |
74 ms |
3672 KB |
contestant found the optimal answer: 4699030287 == 4699030287 |
7 |
Correct |
80 ms |
3676 KB |
contestant found the optimal answer: 12418819758185 == 12418819758185 |
8 |
Correct |
79 ms |
3684 KB |
contestant found the optimal answer: 31093317350 == 31093317350 |
9 |
Correct |
22 ms |
3676 KB |
contestant found the optimal answer: 12194625429236 == 12194625429236 |
10 |
Correct |
39 ms |
3676 KB |
contestant found the optimal answer: 12345131038664 == 12345131038664 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
7256 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
1112 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |