#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long int
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define fir first
#define sec second
#define MAXN 300005
#define mod 998244353
int n, k;
int a[MAXN];
pi solve(int lambda)
{
vector<int> dp(n + 1);
vector<int> cnt(n + 1);
dp[0] = 0;
cnt[0] = 0;
pi best = {0, 0};
pi curr = {0, 0};
auto f = [&](pi x)
{
return dp[x.fir] + x.sec;
};
for (int i = 1; i <= n; i++)
{
dp[i] = dp[i - 1];
cnt[i] = cnt[i - 1];
int id = i - 1;
best.sec += a[id];
if (f(best) < f({i, a[id]}))
{
best = {i, a[id]};
}
int s = dp[best.fir] + best.sec - lambda;
if (s > dp[i])
{
dp[i] = s;
cnt[i] = cnt[best.fir] + 1;
}
}
return {dp[n], cnt[n]};
}
int aliens_trick()
{
int l = 0, r = 1e15;
while (l < r)
{
int mid = (l + r) >> 1;
pi ans = solve(mid);
(ans.sec > k) ? l = mid + 1 : r = mid;
}
pi ans = solve(l);
return ans.fir + (l * k);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> a[i];
cout << aliens_trick() << endl;
return 0;
}
Compilation message
feast.cpp: In function 'std::pair<long long int, long long int> solve(long long int)':
feast.cpp:29:6: warning: variable 'curr' set but not used [-Wunused-but-set-variable]
29 | pi curr = {0, 0};
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
105 ms |
10188 KB |
Output is correct |
2 |
Correct |
108 ms |
10356 KB |
Output is correct |
3 |
Correct |
108 ms |
10500 KB |
Output is correct |
4 |
Correct |
109 ms |
10388 KB |
Output is correct |
5 |
Correct |
108 ms |
10356 KB |
Output is correct |
6 |
Correct |
69 ms |
10172 KB |
Output is correct |
7 |
Correct |
107 ms |
10264 KB |
Output is correct |
8 |
Correct |
89 ms |
10428 KB |
Output is correct |
9 |
Correct |
90 ms |
10320 KB |
Output is correct |
10 |
Correct |
108 ms |
10296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
8544 KB |
Output is correct |
2 |
Correct |
104 ms |
8800 KB |
Output is correct |
3 |
Correct |
101 ms |
8816 KB |
Output is correct |
4 |
Incorrect |
83 ms |
8808 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
132 ms |
10556 KB |
Output is correct |
2 |
Correct |
129 ms |
10404 KB |
Output is correct |
3 |
Correct |
113 ms |
10508 KB |
Output is correct |
4 |
Correct |
112 ms |
10432 KB |
Output is correct |
5 |
Correct |
116 ms |
10756 KB |
Output is correct |
6 |
Correct |
141 ms |
12572 KB |
Output is correct |
7 |
Correct |
137 ms |
10544 KB |
Output is correct |
8 |
Correct |
114 ms |
10544 KB |
Output is correct |
9 |
Correct |
140 ms |
10984 KB |
Output is correct |
10 |
Correct |
138 ms |
10612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
105 ms |
10188 KB |
Output is correct |
2 |
Correct |
108 ms |
10356 KB |
Output is correct |
3 |
Correct |
108 ms |
10500 KB |
Output is correct |
4 |
Correct |
109 ms |
10388 KB |
Output is correct |
5 |
Correct |
108 ms |
10356 KB |
Output is correct |
6 |
Correct |
69 ms |
10172 KB |
Output is correct |
7 |
Correct |
107 ms |
10264 KB |
Output is correct |
8 |
Correct |
89 ms |
10428 KB |
Output is correct |
9 |
Correct |
90 ms |
10320 KB |
Output is correct |
10 |
Correct |
108 ms |
10296 KB |
Output is correct |
11 |
Correct |
104 ms |
8544 KB |
Output is correct |
12 |
Correct |
104 ms |
8800 KB |
Output is correct |
13 |
Correct |
101 ms |
8816 KB |
Output is correct |
14 |
Incorrect |
83 ms |
8808 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |