# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
270129 | kaplanbar | Go (COCI18_go) | C++14 | 255 ms | 173560 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pk {
ll a, b, t;
bool operator<(const Pk other) const {
return a < other.a;
}
} v[105];
int n, m, k;
ll dp[105][105][2005];
ll f(int cur, int far, int T) {
if(T > 2000) return 0;
ll &ret = dp[cur][far][T];
if(~ret) return ret;
ll val = 0;
if(T < v[cur].t) val += v[cur].b;
ret = val;
int d = far > cur ? -1 : 1;
if(cur + d >= 0 && cur + d < m) {
ret = max(ret, val + f(cur + d, far, T + abs(v[cur + d].a - v[cur].a)) );
}
d *= -1;
if(far + d >= 0 && far + d < m) {
ret = max(ret, val + f(far + d, cur, T + abs(v[far+d].a - v[cur].a)) );
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
memset(dp, -1, sizeof dp);
cin >> n >> k >> m;
for(int i = 0; i < m; i++) {
cin >> v[i].a >> v[i].b >> v[i].t;
}
v[m++] = {k, 0, 0};
sort(v, v + m);
for(int i = 0; i < m; i++) {
if(v[i].a == k && v[i].b == 0 && v[i].t == 0) {
cout << f(i,i,0);
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |