oj.uz

Submission #63318

# Submission time Handle Problem Language Result Execution time Memory
63318 2018-08-01T11:23:10 Z MAMBA Go (COCI18_go) C++17
100 / 100
 646 ms 170276 KB 
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define $ system("pause")
#define MOD (ll)10139
#define MAXN 200010
#define MAXM 104
#define MAXK 2003

template<typename T> inline T smin(T &a, const T &b) { return a > b ? a = b : a; }
template<typename T> inline T smax(T &a, const T &b) { return a < b ? a = b : a; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }

ll n, m, k, answer;
ll a[MAXM], b[MAXM], c[MAXM];
ll dp[MAXM][MAXM][2][MAXK];

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> m; 
	bool flag = false;
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i];
		if (a[i] == k) flag = true;
	}
	if (!flag) {
		a[m] = k;
		b[m] = 0;
		c[m] = MAXK - 1;
		for (int i = m - 1; ~i; i--) {
			if (a[i] > a[i + 1]) {
				swap(a[i], a[i + 1]);
				swap(b[i], b[i + 1]);
				swap(c[i], c[i + 1]);
			}
		}
		m++;
	}
	memset(dp, 128, sizeof(dp));
	for (int i = 0; i < m; i++) 
		if (a[i] == k) {
			for (int j = 0; j < MAXK; j++)
				dp[i][i][0][j] = dp[i][i][1][j] = b[i];
			smax(answer, b[i]);
		}
	for (int t = 1; t < MAXK; t++) {
		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j < m; j++) {
				int val1 = 0;
				if (c[i] > t) val1 = b[i];
				int val2 = 0;
				if (c[j] > t) val2 = b[j];
				if ((a[i + 1] - a[i]) <= t)
					smax(dp[i][j][0][t], dp[i + 1][j][0][t - (a[i + 1] - a[i])] + val1);
				if ((a[j]- a[i]) <= t)
					smax(dp[i][j][0][t], dp[i + 1][j][1][t - (a[j] - a[i])] + val1);
				if ((a[j] - a[j - 1]) <= t)
					smax(dp[i][j][1][t], dp[i][j - 1][1][t - (a[j] - a[j - 1])] + val2);
				if ((a[j] - a[i]) <= t)
					smax(dp[i][j][1][t], dp[i][j - 1][0][t - (a[j] - a[i])] + val2);
				smax(answer, dp[i][j][0][t]);
				smax(answer, dp[i][j][1][t]);
			}
		}
	}
	cout << answer << endl;
	//$;
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 169848 KB Output is correct
2 Correct 127 ms 170012 KB Output is correct
3 Correct 130 ms 170048 KB Output is correct
4 Correct 134 ms 170056 KB Output is correct
5 Correct 227 ms 170096 KB Output is correct
6 Correct 291 ms 170156 KB Output is correct
7 Correct 405 ms 170156 KB Output is correct
8 Correct 490 ms 170260 KB Output is correct
9 Correct 558 ms 170276 KB Output is correct
10 Correct 646 ms 170276 KB Output is correct