Submission #63316

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63316	2018-08-01T11:20:28 Z	MAMBA	Go (COCI18_go)	C++14	50 / 100	1000 ms	525312 KB

go

#include <bits/stdc++.h>

using namespace std;

typedef long long 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

50.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	354 ms	333000 KB	Output is correct
2	Correct	286 ms	333256 KB	Output is correct
3	Correct	326 ms	333292 KB	Output is correct
4	Correct	377 ms	333412 KB	Output is correct
5	Correct	900 ms	333492 KB	Output is correct
6	Execution timed out	1132 ms	525312 KB	Time limit exceeded
7	Execution timed out	1133 ms	525312 KB	Time limit exceeded
8	Execution timed out	1128 ms	525312 KB	Time limit exceeded
9	Execution timed out	1160 ms	525312 KB	Time limit exceeded
10	Runtime error	959 ms	525312 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.