oj.uz

Submission #63317

# Submission time Handle Problem Language Result Execution time Memory
63317 2018-08-01T11:21:47 Z MAMBA Go (COCI18_go) C++17
60 / 100
 710 ms 333892 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 103
#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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 166776 KB Output is correct
2 Correct 153 ms 166776 KB Output is correct
3 Correct 169 ms 166816 KB Output is correct
4 Correct 215 ms 166912 KB Output is correct
5 Correct 710 ms 166920 KB Output is correct
6 Runtime error 367 ms 333368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 398 ms 333772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 337 ms 333772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 358 ms 333892 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 649 ms 333892 KB Output is correct