oj.uz

Submission #927610

# Submission time Handle Problem Language Result Execution time Memory
927610 2024-02-15T07:10:45 Z IBory 코알라 (JOI13_koala) C++17
50 / 100
 2000 ms 3784 KB 
#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int MAX = 100007;
ll P[MAX], B[MAX], dp[MAX];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	ll SP, EP, D, A, N;
	cin >> SP >> EP >> D >> A >> N;
	for (int i = 1; i <= N; ++i) cin >> P[i] >> B[i];
	P[0] = SP, P[N + 1] = EP;


	fill(dp + 1, dp + MAX, -2E18);
	map<ll, ll> pv;
	pv[P[0] % D] = 0; 

	for (int i = 1; i <= N + 1; ++i) {
		for (auto [_, p] : pv) dp[i] = max(dp[i], dp[p] - (P[i] - P[p] + D - 1) / D * A);
		dp[i] += B[i];
		pv[P[i] % D] = i;
	}

	// for (int i = 1; i <= N + 1; ++i) {
	// 	for (int j = 0; j < i; ++j) dp[i] = max(dp[i], dp[j] - (P[i] - P[j] + D - 1) / D * A);
	// 	dp[i] += B[i];
	// }

	cout << dp[N + 1] << '\n';
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2904 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 3 ms 2524 KB Output is correct
10 Correct 4 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 2904 KB Output is correct
2 Correct 65 ms 2648 KB Output is correct
3 Correct 11 ms 2652 KB Output is correct
4 Correct 49 ms 2900 KB Output is correct
5 Correct 24 ms 2652 KB Output is correct
6 Correct 18 ms 2652 KB Output is correct
7 Correct 13 ms 2648 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 3784 KB Time limit exceeded
2 Halted 0 ms 0 KB -