Submission #89336

#	Time	Username	Problem	Language	Result	Execution time	Memory
89336		heon	Go (COCI18_go)	C++11	100 / 100	246 ms	160956 KiB

go

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int MOD = 1e9 + 7;

int n, k, m;
vi a,b,c;
ll dp[101][101][2005];

ll f(int x, int y, int t){
	if(t > 2000) return 0;
	if(dp[x][y][t] != -1) return dp[x][y][t];
	ll ret = 0;
	if(x < y){
		if(x != 0) ret = max(ret, f(x - 1, y, t + a[x] - a[x - 1]));
		if(y != m) ret = max(ret, f(y + 1, x, t + a[y] - a[x]));
		if(c[x] > t) ret += b[x];
	}
	else{
		if(x != m) ret = max(ret, f(x + 1, y, t + a[x] - a[x - 1]));
		if(y != 0) ret = max(ret, f(y - 1, x, t + a[x - 1] - a[y - 1]));
		if(c[x - 1] > t) ret += b[x - 1];
	}
	return dp[x][y][t] = ret;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k >> m;
	a.resize(m), b.resize(m), c.resize(m);
	int sind = 0;
	for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i] >> c[i];
		if(a[i] < k) sind = i + 1;
	}
	memset(dp, -1, sizeof(dp));
	ll res = 0;
	if(sind != m) res = max(res, f(sind + 1, sind, a[sind] - k));
	if(sind != 0) res = max(res, f(sind - 1, sind, k - a[sind - 1]));
	cout << res;
}

• Subtask 1: 100 / 100