oj.uz

Submission #1057615

# Submission time Handle Problem Language Result Execution time Memory
1057615 2024-08-14T00:51:33 Z ghostlywalrus Feast (NOI19_feast) C++17
59 / 100
 112 ms 10468 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define int long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())

const int INF = 1e18;
const int maxn = 3e5+10;

int n, k;
int nums[maxn];
int dp[maxn];
int cnt[maxn];

PI solve(int m){
	 for (int i = 0; i <= n; ++i) dp[i] = 0, cnt[i] = 0;
	 int best = 0;
	 int idbest = 0;
		
	 for (int i = 1; i <= n; ++i){
	 	dp[i] = dp[i-1];
		cnt[i] = cnt[i-1];
		best += nums[i];

		if (best-m >= dp[i]){
	 		dp[i] = best-m;
			cnt[i] = cnt[idbest] + 1; 
		}

		if (dp[i] >= best && cnt[i] >= cnt[idbest]){
	 		best = dp[i];
			idbest = i;
		}
	 }

	 return {dp[n], cnt[n]}; 
}


int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;

	for (int i = 1; i <= n; ++i) cin >> nums[i];

	int x = 1e18;
	for (int b = 1e18; b >= 1; b >>= 1){
	 	while (x-b >= 0 && solve(x-b).s <= k) x -= b;
	}

	cout << solve(x).f + k * x << '\n';
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7260 KB Output is correct
2 Correct 52 ms 7260 KB Output is correct
3 Correct 54 ms 7204 KB Output is correct
4 Incorrect 27 ms 7256 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 106 ms 7456 KB Output is correct
2 Correct 104 ms 10332 KB Output is correct
3 Correct 101 ms 10468 KB Output is correct
4 Correct 104 ms 10332 KB Output is correct
5 Correct 112 ms 10468 KB Output is correct
6 Correct 106 ms 10332 KB Output is correct
7 Correct 107 ms 10324 KB Output is correct
8 Correct 104 ms 10332 KB Output is correct
9 Correct 106 ms 10324 KB Output is correct
10 Correct 109 ms 10312 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 0 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 0 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 0 ms 4444 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 0 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 0 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 0 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 0 ms 4444 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 0 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4444 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 4576 KB Output is correct
28 Correct 1 ms 4444 KB Output is correct
29 Correct 1 ms 4696 KB Output is correct
30 Correct 1 ms 4444 KB Output is correct

Subtask #7
0 / 29.0

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