oj.uz

Submission #1104096

# Submission time Handle Problem Language Result Execution time Memory
1104096 2024-10-22T17:40:00 Z ridarfx Feast (NOI19_feast) C++14
30 / 100
 1000 ms 10832 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

int main() {
	int n, k;
	cin >> n >> k;
    long long rk = 0;
	int a[n];
	for (int &i : a) { cin >> i; if(i>=0){
	    rk++;
	} }
    if(k>rk){
        k = rk;
        while(true){
            
        }
    }
	/**
	 * @return the maximum sum along with the number of subarrays used
	 * if creating a subarray penalizes the sum by "lmb" and
	 * there is no limit to the number of subarrays you can create
	 */
	auto solve_lambda = [&](ll lmb) {
		pair<ll, ll> dp[n][2];

		dp[0][0] = {0, 0};
		dp[0][1] = {a[0] - lmb, 1};

		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][0].first + a[i] - lmb, dp[i - 1][0].second + 1),
			        make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
		}

		return max(dp[n - 1][0], dp[n - 1][1]);
	};

	ll lo = 0;
	ll hi = 1e18;
	while (lo < hi) {
		ll mid = (lo + hi + 1) / 2;
		solve_lambda(mid).second >= k ? lo = mid : hi = mid - 1;
	}

	cout << solve_lambda(lo).first + lo * k << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10568 KB Output is correct
2 Correct 122 ms 10792 KB Output is correct
3 Correct 120 ms 10808 KB Output is correct
4 Correct 121 ms 10824 KB Output is correct
5 Correct 127 ms 10796 KB Output is correct
6 Correct 126 ms 10524 KB Output is correct
7 Correct 113 ms 10568 KB Output is correct
8 Correct 117 ms 10796 KB Output is correct
9 Correct 137 ms 10572 KB Output is correct
10 Correct 125 ms 10568 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 10568 KB Output is correct
2 Correct 89 ms 10800 KB Output is correct
3 Correct 84 ms 10528 KB Output is correct
4 Correct 94 ms 10652 KB Output is correct
5 Correct 145 ms 10516 KB Output is correct
6 Correct 86 ms 10516 KB Output is correct
7 Correct 89 ms 10820 KB Output is correct
8 Correct 118 ms 10828 KB Output is correct
9 Correct 115 ms 10568 KB Output is correct
10 Correct 90 ms 10808 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 10824 KB Output is correct
2 Correct 144 ms 10568 KB Output is correct
3 Correct 150 ms 10804 KB Output is correct
4 Correct 143 ms 10532 KB Output is correct
5 Correct 172 ms 10832 KB Output is correct
6 Correct 145 ms 10824 KB Output is correct
7 Correct 147 ms 10824 KB Output is correct
8 Correct 148 ms 10824 KB Output is correct
9 Correct 149 ms 10824 KB Output is correct
10 Correct 180 ms 10824 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 1095 ms 336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 1095 ms 336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Execution timed out 1095 ms 336 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 10568 KB Output is correct
2 Correct 122 ms 10792 KB Output is correct
3 Correct 120 ms 10808 KB Output is correct
4 Correct 121 ms 10824 KB Output is correct
5 Correct 127 ms 10796 KB Output is correct
6 Correct 126 ms 10524 KB Output is correct
7 Correct 113 ms 10568 KB Output is correct
8 Correct 117 ms 10796 KB Output is correct
9 Correct 137 ms 10572 KB Output is correct
10 Correct 125 ms 10568 KB Output is correct
11 Correct 89 ms 10568 KB Output is correct
12 Correct 89 ms 10800 KB Output is correct
13 Correct 84 ms 10528 KB Output is correct
14 Correct 94 ms 10652 KB Output is correct
15 Correct 145 ms 10516 KB Output is correct
16 Correct 86 ms 10516 KB Output is correct
17 Correct 89 ms 10820 KB Output is correct
18 Correct 118 ms 10828 KB Output is correct
19 Correct 115 ms 10568 KB Output is correct
20 Correct 90 ms 10808 KB Output is correct
21 Correct 147 ms 10824 KB Output is correct
22 Correct 144 ms 10568 KB Output is correct
23 Correct 150 ms 10804 KB Output is correct
24 Correct 143 ms 10532 KB Output is correct
25 Correct 172 ms 10832 KB Output is correct
26 Correct 145 ms 10824 KB Output is correct
27 Correct 147 ms 10824 KB Output is correct
28 Correct 148 ms 10824 KB Output is correct
29 Correct 149 ms 10824 KB Output is correct
30 Correct 180 ms 10824 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Execution timed out 1095 ms 336 KB Time limit exceeded
33 Halted 0 ms 0 KB -