/*==============================================================================================================
__ __ _____ ______ _______
| | | | / __ \ / _____| / ______|
__| |__ __| |__ |_| | | | | | |
|__| __| |__| __| | | | |____ | |_____
| | _____ _ | | ____ __ __ ____ _____ _____ / / \ ___ \ | ___ \
| | / _ \ | | | | / _/ | | | | / _ \ / __ \ / _ \ / / | | | | | |
| |_ | |_| | | | | |_ | | | |_| | | |_| | | | | | | |_| | / /___ ____| | | |___| |
\____\ \____/| |_| \____\ |_| \_____/ \_____/ |_| |_| \____ | |______| |______/ \_______/
| |
__/ |
|___/
Pratice, practice, and practice
Where is the bug, delete it there
Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali
You may not be the best, but must be the most effort
Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
Difficult means more time
Done is better than perfect
Pain + Reflection = Progress
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;
ll n, k, a[300005];
pair<ll, ll> dp[300005][3]; //sum doan, cnt doan
ll l, r, ans;
bool check(ll m)
{
dp[0][0]={0, 0};
dp[0][1]={-1e18, 0};
for (ll i=1; i<=n; i++)
{
dp[i][0]=max(dp[i-1][0], dp[i-1][1]);
dp[i][1]=max( make_pair(dp[i-1][1].first+a[i], dp[i-1][1].second), //them a[i] vao doan truoc do
make_pair(dp[i-1][0].first+a[i]-m, dp[i-1][0].second+1)); // bat dau doan moi tai vi tri a[i]
}
return max(dp[n][0], dp[n][1]).second>=k;
}
void solve()
{
cin>>n>>k;
for (ll i=1; i<=n; i++) cin>>a[i];
l=0, r=1e15;
while (l<=r)
{
ld mid=(l+r)/2;
if (check(mid)==true) ans=mid, l=mid+1;
else r=mid-1;
}
check(ans);
cout<<llround(max(dp[n][0], dp[n][1]).first+ans*k);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
clock_t start = clock();
//#ifndef ONLINE_JUDGE
//freopen("_input.txt", "r", stdin);
//freopen("_output.txt", "w", stdout);
//#endif
solve();
clock_t end = clock();
cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
68 ms |
16720 KB |
Output is correct |
| 2 |
Correct |
71 ms |
16720 KB |
Output is correct |
| 3 |
Correct |
71 ms |
16868 KB |
Output is correct |
| 4 |
Correct |
69 ms |
16728 KB |
Output is correct |
| 5 |
Correct |
69 ms |
16728 KB |
Output is correct |
| 6 |
Correct |
69 ms |
16720 KB |
Output is correct |
| 7 |
Correct |
71 ms |
16800 KB |
Output is correct |
| 8 |
Correct |
74 ms |
16604 KB |
Output is correct |
| 9 |
Correct |
67 ms |
16720 KB |
Output is correct |
| 10 |
Correct |
71 ms |
16720 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
60 ms |
16812 KB |
Output is correct |
| 2 |
Correct |
67 ms |
16728 KB |
Output is correct |
| 3 |
Correct |
76 ms |
16720 KB |
Output is correct |
| 4 |
Correct |
64 ms |
16728 KB |
Output is correct |
| 5 |
Correct |
66 ms |
16720 KB |
Output is correct |
| 6 |
Correct |
58 ms |
16728 KB |
Output is correct |
| 7 |
Correct |
62 ms |
16868 KB |
Output is correct |
| 8 |
Correct |
72 ms |
16856 KB |
Output is correct |
| 9 |
Correct |
67 ms |
16728 KB |
Output is correct |
| 10 |
Correct |
73 ms |
16980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
86 ms |
16852 KB |
Output is correct |
| 2 |
Correct |
85 ms |
16724 KB |
Output is correct |
| 3 |
Correct |
84 ms |
16840 KB |
Output is correct |
| 4 |
Correct |
84 ms |
16816 KB |
Output is correct |
| 5 |
Correct |
84 ms |
16832 KB |
Output is correct |
| 6 |
Correct |
86 ms |
16740 KB |
Output is correct |
| 7 |
Correct |
89 ms |
16720 KB |
Output is correct |
| 8 |
Correct |
93 ms |
16840 KB |
Output is correct |
| 9 |
Correct |
88 ms |
16976 KB |
Output is correct |
| 10 |
Correct |
94 ms |
16860 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 29 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2392 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
68 ms |
16720 KB |
Output is correct |
| 2 |
Correct |
71 ms |
16720 KB |
Output is correct |
| 3 |
Correct |
71 ms |
16868 KB |
Output is correct |
| 4 |
Correct |
69 ms |
16728 KB |
Output is correct |
| 5 |
Correct |
69 ms |
16728 KB |
Output is correct |
| 6 |
Correct |
69 ms |
16720 KB |
Output is correct |
| 7 |
Correct |
71 ms |
16800 KB |
Output is correct |
| 8 |
Correct |
74 ms |
16604 KB |
Output is correct |
| 9 |
Correct |
67 ms |
16720 KB |
Output is correct |
| 10 |
Correct |
71 ms |
16720 KB |
Output is correct |
| 11 |
Correct |
60 ms |
16812 KB |
Output is correct |
| 12 |
Correct |
67 ms |
16728 KB |
Output is correct |
| 13 |
Correct |
76 ms |
16720 KB |
Output is correct |
| 14 |
Correct |
64 ms |
16728 KB |
Output is correct |
| 15 |
Correct |
66 ms |
16720 KB |
Output is correct |
| 16 |
Correct |
58 ms |
16728 KB |
Output is correct |
| 17 |
Correct |
62 ms |
16868 KB |
Output is correct |
| 18 |
Correct |
72 ms |
16856 KB |
Output is correct |
| 19 |
Correct |
67 ms |
16728 KB |
Output is correct |
| 20 |
Correct |
73 ms |
16980 KB |
Output is correct |
| 21 |
Correct |
86 ms |
16852 KB |
Output is correct |
| 22 |
Correct |
85 ms |
16724 KB |
Output is correct |
| 23 |
Correct |
84 ms |
16840 KB |
Output is correct |
| 24 |
Correct |
84 ms |
16816 KB |
Output is correct |
| 25 |
Correct |
84 ms |
16832 KB |
Output is correct |
| 26 |
Correct |
86 ms |
16740 KB |
Output is correct |
| 27 |
Correct |
89 ms |
16720 KB |
Output is correct |
| 28 |
Correct |
93 ms |
16840 KB |
Output is correct |
| 29 |
Correct |
88 ms |
16976 KB |
Output is correct |
| 30 |
Correct |
94 ms |
16860 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 35 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 36 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 37 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 38 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 43 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 46 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 48 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 49 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 50 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 52 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 53 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 54 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 55 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 56 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 57 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 58 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 59 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 60 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 61 |
Correct |
118 ms |
16820 KB |
Output is correct |
| 62 |
Correct |
119 ms |
16872 KB |
Output is correct |
| 63 |
Correct |
97 ms |
16808 KB |
Output is correct |
| 64 |
Correct |
123 ms |
16856 KB |
Output is correct |
| 65 |
Correct |
126 ms |
17016 KB |
Output is correct |
| 66 |
Correct |
128 ms |
16976 KB |
Output is correct |
| 67 |
Correct |
119 ms |
16720 KB |
Output is correct |
| 68 |
Correct |
91 ms |
16976 KB |
Output is correct |
| 69 |
Correct |
92 ms |
16808 KB |
Output is correct |
| 70 |
Correct |
87 ms |
16728 KB |
Output is correct |
