Submission #35320

#	Time	Username	Problem	Language	Result	Execution time	Memory
35320		cheater2k	코알라 (JOI13_koala)	C++14	100 / 100	63 ms	5332 KiB

koala

#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 (stderr)

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50