oj.uz

답안 #981174

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981174 2024-05-13T01:11:36 Z beaboss Feast (NOI19_feast) C++14
41 / 100
 12 ms 2140 KB 
// Source: https://oj.uz/problem/view/NOI19_feast
// 

#include "bits/stdc++.h"

using namespace std;
#define FOR(i, a, b) for (ll i = a; i < b; i++)
typedef long long ll;

typedef pair<ll, ll> pii;
#define s second
#define f first

const ll N = 1e5 + 10;
ll a[N];
pii dp[N][2];
ll n, k;

pii solve(ll l) {
	dp[0][0] = {0, 0};
	dp[0][1] = {a[0] - l, 1};

	FOR(i, 1, n) {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		dp[i][1] = max(make_pair(dp[i-1][0].f + a[i] - l, dp[i-1][0].s + 1), make_pair(dp[i-1][1].f + a[i], dp[i-1][1].s));
	}
	return max(dp[n-1][1], dp[n-1][0]);

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> k;

	FOR(i, 0 ,n) cin >> a[i];

	ll lo = 0;
	ll hi = 1e18;

	while (lo < hi) {
		ll m = (lo + hi + 1)/2;
		pii res = solve(m);
		if (res.s >= k) lo = m;
		else hi = m -1;
	}
	// cout << lo << solve(lo).f << endl;
	cout << solve(lo).f + k * lo << endl;

}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 2136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 2140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 2140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 500 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 2136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -