Submission #927593

#	Time	Username	Problem	Language	Result	Execution time	Memory
927593		IBory	코알라 (JOI13_koala)	C++17	30 / 100	2041 ms	6108 KiB

koala

#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;

	map<ll, ll> pv;
	memset(dp, 0xf3, sizeof(dp));
	pv[P[0] % D] = 0; dp[0] = 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;
	}

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

• Subtask 1: 0 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50