| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1103141 |
2024-10-20T09:15:26 Z |
DuongKiet |
Feast (NOI19_feast) |
C++17 |
|
1000 ms |
21464 KB |
#include <bits/stdc++.h>
#define N 300005
#define inf 100000000000000000LL
#define ll long long
#define int long long
#define ii pair <int,long long>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const unsigned ll Mod = 1000000007LL;
int n, k, a[N];
void init(){
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
}
bool ifsub1(){
for (int i = 1; i <= n; i++)
if (a[i] < 0) return 0;
return 1;
}
void sub1(){
int ans = 0;
for (int i = 1; i <= n; i++)
ans += a[i];
cout << ans << '\n';
}
int pos;
bool ifsub2(){
int cnt = 0;
for (int i = 1; i <= n; i++)
if (a[i] < 0) {pos = a[i]; cnt++;}
return (cnt < 2);
}
void sub2(){
int sum = 0, suml = 0, am = 0;
bool kt = 0;
for (int i = 1; i <= n; i++){
if (a[i] < 0) {
kt = 1;
am = a[i];
}
if (!kt) suml += a[i];
sum += a[i];
}
if (k > 1)
cout << sum - am << '\n';
else cout << max(suml, max(sum, sum - suml - am));
}
void sub3(){
int ans = 0, res = 0;
for (int i = 1; i <= n; i++) {
res = max(0ll, res + a[i]);
ans = max(ans, res);
}
cout << ans << '\n';
}
//int pa[N], sz[N];
//int findpa(int u){
//
// if (u == pa[u]) return u;
// return pa[u] = findpa(pa[u]);
//}
//void Union(int a, int b){
//
// a = findpa(a);
// b = findpa(b);
// if (a == b) return;
// if (sz[a] < sz[b]) swap(a,b);
// pa[b] = a;
// sz[a] += sz[b];
// sum[a] += sum[b];
//}
//vector <ii> d;
//void Add(int u){
// d.pb({u, sum[u]});
//}
//void sub6(){
// for (int i = 1; i <= n; i++){
// pa[i] = i;
// sz[i] = 1;
// sum[i] = a[i];
// }
// int parduong, param;
// bool task = 0;
// if (a[1] >= 0) {parduong = 1; task = 1;}
// else param = 1;
// for (int i = 1; i <= n; i++){
// if (a[i] >= 0) {
// if (task)
// Union(parduong, i);
// else parduong = i;
// task = 1;
// }
// else {
// if (!task) Union(param, i);
// else param = i;
// task = 0;
// }
// }
// int curpa = findpa(1);
// Add(curpa);
// for (int i = 1; i <= n; i++){
// int u = findpa(i);
// if (u != curpa){
// curpa = u;
// Add(u);
// }
// }
// for (int i = 2; i < d.size(); i++){
// if (d[i].se > 0 && d[i-2].se > 0){
// g.pb({d[i].fi, d[i - 2].fi, d[i].se + d[i].se });
// }
// }
//}
pair<long double, int> dp[N + 1][2];
bool check(long double res) {
dp[0][0] = {0, 0}, dp[0][1] = {-inf, 0};
for (int 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),
make_pair(dp[i - 1][0].first + a[i] - res, dp[i - 1][0].second + 1));
}
return max(dp[n][0], dp[n][1]).second >= k;
};
void solve(){
const long double EPS = 1e-3;
int lower = 0, upper = inf;
while (lower + EPS < upper) {
int mid = (lower + upper) / 2;
if (check(mid)) {
lower = mid;
} else {
upper = mid;
}
}
int res = lower;
check(res);
cout << res * k + max(dp[n][0].first, dp[n][1].first);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
#define nametask "PRESUFF"
if(fopen(nametask".inp", "r")) {
freopen(nametask".inp", "r", stdin);
freopen(nametask".out", "w", stdout);
}
init();
// if (ifsub1()) return sub1(), 0;
// if (ifsub2()) return sub2(), 0;
// if (k == 1) return sub3(), 0;
// if (k <= n && n <= 2000) return sub6(), 0;
solve();
return 0;
}
/// Duong Anh Kiet from Kien Giang ///
/*
6 1
-1 -2 -1 2 -1 2
*/
Compilation message
feast.cpp: In function 'int main()':
feast.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(nametask".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen(nametask".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
21320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
21328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1052 ms |
21464 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
2384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
2384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
2384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
350 ms |
21320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
