# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
949039 |
2024-03-18T20:40:57 Z |
alexdd |
Feast (NOI19_feast) |
C++17 |
|
351 ms |
12756 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long double ld;
const int INF = 1e9;
int n,k;
int a[300005];
int dp[300005];
int cnt[300005];
int pref[300005];
ld coef;
void solve()
{
int mxm=0,cate=0;
for(int i=1;i<=n;i++)
{
pref[i] = pref[i-1] + a[i];
dp[i] = dp[i-1];
cnt[i] = cnt[i-1];
int aux = mxm + pref[i] - coef;
if(aux>dp[i] || (aux==dp[i] && cate+1<cnt[i]))
{
dp[i] = aux;
cnt[i] = cate+1;
}
if(dp[i]-pref[i]>mxm || (dp[i]-pref[i]==mxm && cate<cnt[i]))
{
mxm = dp[i]-pref[i];
cate = cnt[i];
}
}
}
/**
dp[i] = max(dp[x] - pref[x]) + pref[i] - coef
*/
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
ld st,dr;
st=-INF;
dr=INF;
for(int it=0;it<100;it++)
{
coef = (st+dr)/2.0;
solve();
if(cnt[n]>=k)
st=coef;
else
dr=coef;
}
cout<<max((int)0,(int)(dp[n] + cnt[n]*coef));
//cout<<dp[n] + k*coef;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
192 ms |
12368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
10576 KB |
Output is correct |
2 |
Correct |
133 ms |
10936 KB |
Output is correct |
3 |
Correct |
126 ms |
10576 KB |
Output is correct |
4 |
Incorrect |
154 ms |
10816 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
351 ms |
12756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
192 ms |
12368 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |