oj.uz

답안 #26874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26874 2017-07-06T17:39:05 Z abcdef6199 코알라 (JOI13_koala) C++
100 / 100
 153 ms 7916 KB 
#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

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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7916 KB Output is correct
2 Correct 0 ms 7916 KB Output is correct
3 Correct 0 ms 7916 KB Output is correct
4 Correct 0 ms 7916 KB Output is correct
5 Correct 0 ms 7916 KB Output is correct
6 Correct 0 ms 7916 KB Output is correct
7 Correct 0 ms 7916 KB Output is correct
8 Correct 0 ms 7916 KB Output is correct
9 Correct 0 ms 7916 KB Output is correct
10 Correct 0 ms 7916 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 7916 KB Output is correct
2 Correct 119 ms 7916 KB Output is correct
3 Correct 29 ms 7916 KB Output is correct
4 Correct 96 ms 7916 KB Output is correct
5 Correct 43 ms 7916 KB Output is correct
6 Correct 29 ms 7916 KB Output is correct
7 Correct 53 ms 7916 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 7916 KB Output is correct
2 Correct 153 ms 7916 KB Output is correct
3 Correct 129 ms 7916 KB Output is correct
4 Correct 116 ms 7916 KB Output is correct
5 Correct 93 ms 7916 KB Output is correct
6 Correct 66 ms 7916 KB Output is correct