oj.uz

답안 #995250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995250 2024-06-08T17:40:07 Z Yarema Feast (NOI19_feast) C++17
12 / 100
 70 ms 1628 KB 
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;
typedef double db;

const int INF = 1e9 + 47;

PLI f(VI& a, int lambda)
{
	int n = SZ(a);
	PLI dp0 = {0, 0};
	PLI dp1 = {-INF, 0};
	FOR (i, 0, n)
	{
		PLI ndp0 = max(dp0, dp1);
		PLI ndp1 = max(PLI(dp0.F + a[i] - lambda, dp0.S + 1), PLI(dp1.F + a[i], dp1.S));
		
		dp0 = ndp0;
		dp1 = ndp1;
		//cerr << i << ' ' << dp0.F << ' ' << dp0.S << ' ' << dp1.F << ' ' << dp1.S << '\n';
	}
	return max(dp0, dp1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	VI a(n);
	FOR (i, 0, n)
		cin >> a[i];
	
	
	LL l = -1, r = INF;
	while (l + 1 < r)
	{
		int m = (l + r) / 2;
		auto [val, cnt] = f(a, m);
		if (cnt > k)
			l = m;
		else
			r = m;
	}
	//cerr << r << '\n';
	auto [val, cnt] = f(a, r);
	cout << val + cnt * r << '\n';
	
	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1368 KB Output is correct
2 Correct 31 ms 1628 KB Output is correct
3 Correct 32 ms 1624 KB Output is correct
4 Correct 31 ms 1628 KB Output is correct
5 Correct 32 ms 1368 KB Output is correct
6 Correct 33 ms 1372 KB Output is correct
7 Correct 30 ms 1368 KB Output is correct
8 Correct 31 ms 1624 KB Output is correct
9 Correct 31 ms 1372 KB Output is correct
10 Correct 31 ms 1372 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1372 KB Output is correct
2 Correct 26 ms 1624 KB Output is correct
3 Correct 24 ms 1372 KB Output is correct
4 Correct 24 ms 1372 KB Output is correct
5 Correct 31 ms 1368 KB Output is correct
6 Correct 25 ms 1372 KB Output is correct
7 Correct 25 ms 1628 KB Output is correct
8 Correct 33 ms 1628 KB Output is correct
9 Correct 31 ms 1368 KB Output is correct
10 Correct 27 ms 1372 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1368 KB Output is correct
2 Correct 31 ms 1628 KB Output is correct
3 Correct 32 ms 1624 KB Output is correct
4 Correct 31 ms 1628 KB Output is correct
5 Correct 32 ms 1368 KB Output is correct
6 Correct 33 ms 1372 KB Output is correct
7 Correct 30 ms 1368 KB Output is correct
8 Correct 31 ms 1624 KB Output is correct
9 Correct 31 ms 1372 KB Output is correct
10 Correct 31 ms 1372 KB Output is correct
11 Correct 24 ms 1372 KB Output is correct
12 Correct 26 ms 1624 KB Output is correct
13 Correct 24 ms 1372 KB Output is correct
14 Correct 24 ms 1372 KB Output is correct
15 Correct 31 ms 1368 KB Output is correct
16 Correct 25 ms 1372 KB Output is correct
17 Correct 25 ms 1628 KB Output is correct
18 Correct 33 ms 1628 KB Output is correct
19 Correct 31 ms 1368 KB Output is correct
20 Correct 27 ms 1372 KB Output is correct
21 Incorrect 70 ms 1372 KB Output isn't correct
22 Halted 0 ms 0 KB -