# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
89336 |
2018-12-11T18:28:22 Z |
heon |
Go (COCI18_go) |
C++11 |
|
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 |