This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 107
int n, mingrp, maxgrp;
int arr[MAX], dp[MAX][MAX][MAX], psum[MAX];
#define fyou LLONG_MAX/5
inline int sumarr(int a, int b){
int sum = psum[b]; if (a != 0) sum -= psum[a-1];
return sum;
}
int recur(int idx, int prevCut, int grpCount){
if (idx == n-1){
grpCount++;
if (grpCount >= mingrp && grpCount <= maxgrp) return sumarr(prevCut, n-1);
else return fyou;
}
if (dp[idx][prevCut][grpCount] != -1) return dp[idx][prevCut][grpCount];
int ans = 0;
//choose cut or no cut
int a = recur(idx+1, prevCut, grpCount);
int b = recur(idx+1, idx+1, grpCount+1);
if (a == fyou && b == fyou) ans = a;
else if (a == fyou) ans = b;
else if (b == fyou) ans = a;
else ans = min(a, b | sumarr(prevCut, idx));
return dp[idx][prevCut][grpCount] = ans;
}
main(){
cin >> n >> mingrp >> maxgrp;
for (int x = 0; x < n; x++){
cin >> arr[x];
}
psum[0] = arr[0]; for (int x = 1; x < n; x++) psum[x] = psum[x-1] + arr[x];
memset(dp, -1, sizeof(dp));
assert(recur(0, 0, 0) != fyou);
cout << recur(0, 0, 0);
}
Compilation message (stderr)
sculpture.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
38 | main(){
| ^~~~
# | 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... |