Submission #26874

#	Time	Username	Problem	Language	Result	Execution time	Memory
26874		abcdef6199	코알라 (JOI13_koala)	C++98	100 / 100	153 ms	7916 KiB

koala

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

typedef long long LL;
typedef pair<int, int> II;

const int MAXN = (int) 1e5 + 10;
int n, d, cost, a[MAXN], b[MAXN], c[MAXN];
LL dp[MAXN];

#define mid ((l + r) >> 1)
const LL INF = 1e18;
struct SegTree {
	LL S[MAXN * 5];
	void Build(int k, int l, int r) {
		if (l == r) {
			S[k] = -INF;
			return;
		}
		Build(k << 1 | 0, l, mid);
		Build(k << 1 | 1, mid + 1, r);
		S[k] = max(S[k << 1], S[k << 1 | 1]);
	}
	void Update(int k, int l, int r, int i, LL v) {
		if (l == r) {
			S[k] = v;
			return;
		}
		if (i <= mid) Update(k << 1, l, mid, i, v);
		else Update(k << 1 | 1, mid + 1, r, i, v);
		S[k] = max(S[k << 1], S[k << 1 | 1]);
	}
	LL Query(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return -INF;
		if (i <= l && r <= j) return S[k];
		return max(Query(k << 1, l, mid, i, j), Query(k << 1 | 1, mid + 1, r, i, j));
	}
} ST;
#undef mid

int main() {
	int s, t; scanf("%d%d", &s, &t);
	scanf("%d%d%d", &d, &cost, &n); n += 2;
	for (int i = 2; i <= n - 1; ++i) scanf("%d%d", &a[i], &b[i]);
	a[1] = s; b[1] = 0;
	a[n] = t; b[n] = 0;

	for (int i = 1; i <= n; ++i) c[i] = a[i] % d;
	sort(c + 1, c + 1 + n);

	ST.Build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		if (i > 1) {
			int pos = lower_bound(c + 1, c + 1 + n, a[i] % d) - c;
			LL f1 = ST.Query(1, 1, n, 1, pos - 1) - cost;
			LL f2 = ST.Query(1, 1, n, pos, n);
			dp[i] = max(f1, f2) - cost * LL(a[i] / d) + b[i];
		}
		ST.Update(1, 1, n, lower_bound(c + 1, c + 1 + n, a[i] % d) - c, dp[i] + cost * LL(a[i] / d));
	}
	// for (int i = 1; i <= n; ++i) cout << dp[i] << " "; cout << endl;

	cout << dp[n];
	return 0;
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:42:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int s, t; scanf("%d%d", &s, &t);
                                 ^
koala.cpp:43:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &d, &cost, &n); n += 2;
                                ^
koala.cpp:44:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 2; i <= n - 1; ++i) scanf("%d%d", &a[i], &b[i]);
                                                              ^

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