oj.uz

답안 #35320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35320 2017-11-20T07:59:34 Z cheater2k 코알라 (JOI13_koala) C++14
100 / 100
 63 ms 5332 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 100020;
const long long inf = 1e18;

int K, M, D, A, N;
vector<int> z;
int T[MAX], B[MAX];

long long T1[MAX], T2[MAX];

void upd1(int x, long long v) { for (; x < MAX; x += x & -x) T1[x] = min(T1[x], v); }
long long get1(int x) { long long res = inf; for (; x > 0; x -= x & -x) res = min(res, T1[x]); return res; } 
void upd2(int x, long long v) { for (; x > 0; x -= x & -x) T2[x] = min(T2[x], v); }
long long get2(int x) { long long res = inf; for (; x < MAX; x += x & -x) res = min(res, T2[x]); return res; }

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> K >> M >> D >> A >> N;
	z.push_back(0);
	for (int i = 1; i <= N; ++i) {
		cin >> T[i] >> B[i]; T[i] -= K;
		z.push_back(T[i] % D);
	}
	M -= K; T[N + 1] = M; z.push_back(M % D);
	sort(z.begin(), z.end());
	z.resize(distance(z.begin(), unique(z.begin(), z.end())));

	for (int i = 0; i < MAX; ++i) T1[i] = T2[i] = inf;
	upd1(1, 0);
	upd2(1, 0);

	long long f;
	for (int i = 1; i <= N + 1; ++i) {
		int md = lower_bound(z.begin(), z.end(), T[i] % D) - z.begin() + 1;
		f = 1LL * (T[i] / D) * A - B[i] + get2(md);
		f = min(f, 1LL * (T[i] / D) * A + A - B[i] + get1(md - 1));
		upd1(md, f - 1LL * (T[i] / D) * A);
		upd2(md, f - 1LL * (T[i] / D) * A);
	}

	cout << -f << '\n';
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:43:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout << -f << '\n';
           ^

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 5332 KB Output is correct
2 Correct 39 ms 5332 KB Output is correct
3 Correct 23 ms 4944 KB Output is correct
4 Correct 43 ms 5332 KB Output is correct
5 Correct 23 ms 4944 KB Output is correct
6 Correct 16 ms 4944 KB Output is correct
7 Correct 29 ms 5332 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 5332 KB Output is correct
2 Correct 53 ms 5332 KB Output is correct
3 Correct 46 ms 5332 KB Output is correct
4 Correct 53 ms 5332 KB Output is correct
5 Correct 46 ms 4944 KB Output is correct
6 Correct 26 ms 4944 KB Output is correct