#include <bits/stdc++.h>
using namespace std;
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a))
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int mxN=5e3+5;
int dp[105][105][2000], t[105], v[105], h[105], n, m, k;
// left = 1, right = 0;
int solve(int l, int r, int time, bool dir){
int ret1=0, ret2=0;
if(dir){
if(l-1 >= 1)
ret1 = solve(l-1, r, time+abs(h[l]-h[l-1]), 1)+(time + abs(h[l]-h[l-1]) < t[l-1] ? v[l-1]:0);
if(r <= m)
ret2 = solve(l-1, r, time+abs(h[l]-h[r]), 0) + (time + abs(h[l]-h[r]) < t[r] ? v[r]:0);
return max(ret1, ret2);
}
else{
if(l >= 1)
ret1 = solve(l, r+1, time+abs(h[r]-h[l]), 1)+(time + abs(h[r]-h[l]) < t[l] ? v[l]:0);
if(r+1 <= m)
ret2 = solve(l, r+1, time+abs(h[r]-h[r+1]), 0) + (time + abs(h[r]-h[r+1]) < t[r+1] ? v[r+1]:0);
return max(ret1, ret2);
}
}
int main(){
cin >> n >> k >> m;
int st=-1;
for(int i=1; i<=m; i++){
cin >> h[i] >> v[i] >> t[i];
if(h[i] >= k && st==-1)
st=i;
}
cout << max(solve(st-1, st, abs(k-h[st-1]), 1)+(abs(k-h[st-1]) < t[st-1] ? v[st-1]:0), solve(st-1, st, abs(k-h[st]), 0) + (abs(k-h[st]) < t[st] ? v[st]:0));
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
308 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
304 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Execution timed out |
1093 ms |
212 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1077 ms |
212 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1086 ms |
212 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1091 ms |
212 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1084 ms |
212 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1082 ms |
212 KB |
Time limit exceeded |
