답안 #89336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89336 2018-12-11T18:28:22 Z heon Go (COCI18_go) C++11
100 / 100
246 ms 160956 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 160504 KB Output is correct
2 Correct 144 ms 160504 KB Output is correct
3 Correct 138 ms 160596 KB Output is correct
4 Correct 143 ms 160680 KB Output is correct
5 Correct 161 ms 160680 KB Output is correct
6 Correct 160 ms 160684 KB Output is correct
7 Correct 199 ms 160860 KB Output is correct
8 Correct 227 ms 160920 KB Output is correct
9 Correct 246 ms 160956 KB Output is correct
10 Correct 224 ms 160956 KB Output is correct