Submission #427886

#	Time	Username	Problem	Language	Result	Execution time	Memory
427886		Kevin_Zhang_TW	Long Distance Coach (JOI17_coach)	C++17	46 / 100	2045 ms	460 KiB

coach

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing

const int MAX_N = 300010;
const ll inf = 2e18;

ll X, n, m, W, T;
ll s[MAX_N];

ll dp[MAX_N], sp[MAX_N];

pair<ll,ll> man[MAX_N];

ll cost(int l, int r) {
	if (l > r) return 0;
	ll req = X / T + 10;
	ll ret = 0;
	for (int i = r;i >= l;--i) {
		chmin(req, sp[i]);
		ret += W * req + man[i].second;
	}
	return ret;
}

// N refill points, and M people
// remember the driver need water too
void solve() {
	fill(dp, dp + m, inf);
	fill(sp, sp + m, X / T + 10);
	sort(s, s + n);
	sort(man, man + m);

	for (int i = 0;i < n;++i) {
		ll spt = s[i] / T;
		int p = lower_bound(man, man + m, make_pair(s[i] % T, 0ll)) - man;
		DE(i, spt, s[i] % T, man[p-1].first);
		chmin(sp[p-1], spt);
	}
	for (int i = 0;i < m;++i)
		DE(i, sp[i]);

	for (int i = 0;i < m;++i) {
		auto [d, c] = man[i];
		ll sum = (X / T + (X % T > d)) * W;
		for (int j = 0;j < i;++j) {
			chmin(dp[i], sum + cost(j+1, i-1) + dp[j]);
		}
		chmin(dp[i], sum + cost(0, i-1));

		DE(i, sum, d, c, dp[i]);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> X >> n >> m >> W >> T;

	DE(X, n, m, W, T);
	for (int i = 0;i < n;++i)
		cin >> s[i];
	s[n++] = X;

	for (int i = 0;i < m;++i) {
		auto &[d, c] = man[i];
		cin >> d >> c;
	}
	man[m++] = make_pair(0, inf);
	
	solve();

	ll res = inf;
	for (int i = 0;i < m;++i) {
		chmin(res, dp[i] + cost(i+1, m-1));
	}

	cout << res << '\n';
}

Compilation message (stderr)

coach.cpp: In function 'void solve()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:56:3: note: in expansion of macro 'DE'
   56 |   DE(i, spt, s[i] % T, man[p-1].first);
      |   ^~
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:60:3: note: in expansion of macro 'DE'
   60 |   DE(i, sp[i]);
      |   ^~
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:70:3: note: in expansion of macro 'DE'
   70 |   DE(i, sum, d, c, dp[i]);
      |   ^~
coach.cpp: In function 'int32_t main()':
coach.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
coach.cpp:78:2: note: in expansion of macro 'DE'
   78 |  DE(X, n, m, W, T);
      |  ^~

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29