Submission #337998

#	Time	Username	Problem	Language	Result	Execution time	Memory
337998		Kevin_Zhang_TW	Toll (BOI17_toll)	C++17	0 / 100	108 ms	66796 KiB

toll

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 50010, MAX_L = 16, MAX_K = 10;
const ll inf = 1ll << 55, bound = 1ll << 50;
vector<int> edge[MAX_N];

int K, n, m, q;
ll dp[MAX_L][MAX_N][MAX_K];
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> K >> n >> m >> q;
	K <<= 1;
	for (int d = 0;1<<d <= n;++d) 
		for (int i = 0;i < n;++i) 
			for (int j = 0;j < K;++j)
				dp[d][i][j] = inf;

	for (int i = 0;i < n;++i) dp[0][i][0] = 0;

	for (int a, b, t, i = 0;i < m;++i) {
		cin >> a >> b >> t;
		for (int d = 0;1<<d <= b - a + 1;++d) 
			chmin(dp[d][a][b - a - (1<<d) + 1], (ll)t);
	}

	for (int i = 0;i < m;++i) {
		for (int k = 0;k < K;++k) {
			for (int l = 0;l + k < K;++l)
				chmin(dp[0][i][l + k], dp[0][i][k] + dp[0][ i + k ][l]);
		}
	}

	for (int d = 1;1<<d <= n;++d) {
		for (int i = 0;i < n;++i) {
			for (int k = 0;k < K;++k)
				for (int l = 0;l + max(0, k - 1) < K;++l) if (l + k)
					chmin(dp[d][i][l + k - 1],
						   	dp[d-1][i][k] + dp[d-1][ min(n-1, i-1 + (1<<d>>1) + k) ][l]);

//			for (int k = 0;k < K;++k) if (dp[d][i][k] < bound)
//				DE(d, i, i + (1<<d) - 1 + k, k, dp[d][i][k]);
		}
	}

	auto qry = [&](int a, int b) -> ll {
		int dis = b - a;
		if (dis < K) return dp[0][a][b - a];
		dis -= K - 1;

		ll *cost = new ll[K]{}, *tmp = new ll[K];

		fill(cost+1, cost+K, inf);


		for (int d = 0;1<<d <= dis;++d) if (dis >> d & 1) {
			fill(tmp, tmp + K, inf);

			//DE(a, a + K - 1, d);
			for (int k = 0;k < K;++k)
				for (int l = 0;l + max(0, k - 1) < K;++l) if (l + k && dp[d][ a + k ][l] < bound) {
					chmin(tmp[l + k - 1],
							cost[k] + dp[d][ a + k ][l]);
				}
			a += 1 << d;
			swap(cost, tmp);

		//DE(a, b), debug(cost, cost + K);
		}
		//DE(a, b), debug(cost, cost + K);
		return cost[K - 1];

	};
	while (q--) {
		int a, b;
		cin >> a >> b;
		ll res = qry(a, b);
		DE(a, b, res);
		cout << (res > bound ? -1 : res) << '\n';
	}
}

Compilation message (stderr)

toll.cpp: In function 'int32_t main()':
toll.cpp:20:17: warning: statement has no effect [-Wunused-value]
   20 | #define DE(...) 0
      |                 ^
toll.cpp:102:3: note: in expansion of macro 'DE'
  102 |   DE(a, b, res);
      |   ^~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44