Submission #1189361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189361		JooDdae	코알라 (JOI13_koala)	C++20	100 / 100	65 ms	5828 KiB

koala

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

const ll INF = 1e18;

int p[100100], e, d, n;
ll a;
vector<int> v;

int lb(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }

ll dp[100100], t[400400], b[100100];

void update(int id, ll x, int node = 1, int l = 0, int r = v.size()-1) {
	if(id < l || r < id) return;
	if(l == r) {
		t[node] = max(t[node], x);
		return;
	}
	update(id, x, node*2, l, mid), update(id, x, node*2+1, mid+1, r);
	t[node] = max(t[node*2], t[node*2+1]);
}

ll find(int nl, int nr, int node = 1, int l = 0, int r = v.size()-1) {
	if(nr < l || r < nl) return -INF;
	if(nl <= l && r <= nr) return t[node];
	return max(find(nl, nr, node*2, l, mid), find(nl, nr, node*2+1, mid+1, r));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> p[0] >> e >> d >> a >> n;
	for(int i=1;i<=n;i++) cin >> p[i] >> b[i];
	p[++n] = e;

	for(int i=0;i<=n;i++) v.push_back(p[i] % d);
	sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());

	fill(t+1, t+v.size()*4+1, -INF);
	update(lb(p[0] % d), p[0]/d*a);
	for(int i=1;i<=n;i++) {
		int X = lb(p[i] % d);
		dp[i] = b[i] - p[i]/d*a + max(find(0, X-1) - a, find(X, v.size()-1));
		update(X, dp[i] + p[i]/d*a);
	}

	cout << dp[n];
}

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