oj.uz

Submission #1017454

# Submission time Handle Problem Language Result Execution time Memory
1017454 2024-07-09T08:08:02 Z anHiep Feast (NOI19_feast) C++14
18 / 100
 87 ms 15184 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "Orz_chUoNgnn_khanhtb_0x2ee08"
#endif

using namespace std;

#define int long long
#define fi first 
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vi vector<int> 
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 3e5;
int tc, tt = 1;

int n, k;
int a[N + 5];
ll dp[N + 5][2], cnt[N + 5][2];
void solve() {
	cin>>n>>k;
	for(int i=1; i<=n; i++) cin>>a[i];
	int l = 0, r = 1e18;
	ll ans = 0;
	while(l <= r) {
		int mid = (l + r)/2;
		dp[1][0] = 0;
		dp[1][1] = a[1] - mid;
		cnt[1][0] = 0;
		cnt[1][1] = 1;
		for(int i=2; i<=n; i++) {
			ll v1 = dp[i - 1][0] + a[i] - mid;
			ll v2 = dp[i - 1][1] + a[i];
			dp[i][1] = max(v1, v2);
			if(v1 == v2) cnt[i][1] = max(cnt[i - 1][0] + 1, cnt[i - 1][1]);
			else {
				if(dp[i][1] == v1) cnt[i][1] = cnt[i - 1][0] + 1;
				else cnt[i][1] = cnt[i - 1][1];
			}

			v1 = dp[i - 1][0];
			v2 = dp[i - 1][1];
			dp[i][0] = max(v1, v2);
			if(v1 == v2) cnt[i][0] = max(cnt[i - 1][0], cnt[i - 1][1]);
			else {
				if(dp[i][0] == v1) cnt[i][0] = cnt[i - 1][0];
				else cnt[i][0] = cnt[i - 1][1];
			}
		}
		ll seg = (dp[n][0] > dp[n][1] ? cnt[n][0] : cnt[n][1]);
		if(dp[n][0] == dp[n][1]) {
			if(cnt[n][0] == k) ans = max(ans, dp[n][0] + cnt[n][0] * mid);
			if(cnt[n][1] == k) ans = max(ans, dp[n][1] + cnt[n][1] * mid);
			seg = max(cnt[n][0], cnt[n][1]);
		}
		if(seg > k) l = mid + 1;
		else {
			if(seg == k)
				ans = max(ans, max(dp[n][0], dp[n][1]) + mid * seg);
			r = mid - 1;
		}	
	}
	cout<<ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".INP", "r", stdin);
    // freopen(".OUT", "w", stdout);
    for(tc=1; tc<=tt; tc++) solve();
    cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11868 KB Output is correct
2 Correct 54 ms 13300 KB Output is correct
3 Correct 57 ms 12996 KB Output is correct
4 Incorrect 51 ms 12892 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 12048 KB Output is correct
2 Correct 83 ms 14876 KB Output is correct
3 Correct 86 ms 14928 KB Output is correct
4 Correct 80 ms 14892 KB Output is correct
5 Correct 81 ms 14932 KB Output is correct
6 Correct 80 ms 14932 KB Output is correct
7 Correct 81 ms 14936 KB Output is correct
8 Correct 87 ms 14932 KB Output is correct
9 Correct 81 ms 15184 KB Output is correct
10 Correct 82 ms 14940 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 11.0

# Verdict Execution time Memory 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 -

Subtask #6
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -