# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
638644 |
2022-09-06T15:23:13 Z |
VitaliyFS |
Feast (NOI19_feast) |
C++17 |
|
4 ms |
596 KB |
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
const ll INF = 1000000007, DIM = 2007, DIM2 = 107, MAXN = 100007, MOD = 1000000007;
ll tt, mid, res,f, y, t, w,c,root, res1, res2, p[DIM], tin[DIM],ans[DIM], pref[DIM], sz[DIM], tout[DIM], type, a[DIM], b[DIM], ptr, cnt[DIM], sum, pos, h, sx,sy, id, testcase, curans, nn, split, n, m, x, k1, k2, changecnt,k,l,r,v,u, l1,r1,l2,r2;
bool flag, flag2;
pll dp[DIM];
bool good(ll x) {
sum=0;
for(int i=1;i<=n;i++){
dp[i]={-INF,0};
sum=0;
for(int j=i-1;j>=0;j--) {
sum+=a[j+1];
for(int k=j;k>=0;k--) {
if((dp[k].fr+sum+x>dp[i].fr)||(dp[k].fr+sum+x==dp[i].fr&&dp[k].sc + 1 < dp[i].sc)){
dp[i].fr = dp[k].fr+sum+x;
dp[i].sc = dp[k].sc + 1;
}
}
}
}
res1 = -INF, res2 = INF;
for(int i=1;i<=n;i++) {
if(dp[i].fr > res1 || (dp[i].fr == res && dp[i].sc < res2)){
res1=dp[i].fr;res2=dp[i].sc;
}
}
return res2 >= k;
}
void solve() {
cin>>n>>k;
for(int i=1;i<=n;i++){cin>>a[i];pref[i]=pref[i-1]+a[i];}
l=-INF;r=INF;
while(l<r){
mid=(l+r)>>1;
if(!good(mid))l=mid+1;
else r=mid;
}
good(l);
cout<<max(res1-k*l,0ll)<<'\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
tt=1;
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
//cin>>tt;
while(tt--) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |