#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define sz(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
#define cint int&
using namespace std;
const int nax = 2010;
const int inf = 1e9;
void maxi(int &a, int b) {
a = max(a, b);
}
int n, k, m;
int a[nax], b[nax], c[nax];
int dp[101][101][2001][2]; // dp[l][r][t] maksymalny wynik, jeśli odwiedziliśmy od l do r budynku do czasu t i jestemy w czyms :0
int main() {
scanf ("%d%d%d", &n, &k, &m);
rep(l, 1, m)
rep(r, 1, m)
rep(t, 0, 2000)
rep(g, 0, 1)
dp[l][r][t][g] = -inf;
rep(i, 1, m) {
scanf ("%d%d%d", a + i, b + i, c + i);
int czas = abs(k - a[i]) + 1;
dp[i][i][czas][0] = (czas <= c[i] ? b[i] : 0);
}
int res = 0;
rep(len, 1, m)
rep(l, 1, m - len + 1) {
int r = l + len - 1;
rep(czas, 0, 2000) {
maxi(res, dp[l][r][czas][0]);
maxi(res, dp[l][r][czas][1]);
int l1 = abs(a[l] - a[l - 1]);
int l2 = abs(a[r] - a[l - 1]);
int r1 = abs(a[r + 1] - a[l]);
int r2 = abs(a[r + 1] - a[r]);
if (l != 1) {
if (czas + l1 <= 2000)
maxi(dp[l - 1][r][czas + l1][0], dp[l][r][czas][0] + (czas + l1 <= c[l - 1] ? b[l - 1] : 0));
if (czas + l2 <= 2000)
maxi(dp[l - 1][r][czas + l2][0], dp[l][r][czas][1] + (czas + l2 <= c[l - 1] ? b[l - 1] : 0));
}
if (r != m) {
if (czas + r1 <= 2000)
maxi(dp[l][r + 1][czas + r1][1], dp[l][r][czas][0] + (czas + r1 <= c[r + 1] ? b[r + 1] : 0));
if (czas + r2 <= 2000)
maxi(dp[l][r + 1][czas + r2][1], dp[l][r][czas][1] + (czas + r2 <= c[r + 1] ? b[r + 1] : 0));
}
}
}
printf ("%d\n", res);
return 0;
}
Compilation message
go.cpp: In function 'int main()':
go.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", &n, &k, &m);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~
go.cpp:37:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d%d", a + i, b + i, c + i);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1920 KB |
Output is correct |
| 3 |
Correct |
9 ms |
3456 KB |
Output is correct |
| 4 |
Correct |
14 ms |
6784 KB |
Output is correct |
| 5 |
Correct |
67 ms |
39808 KB |
Output is correct |
| 6 |
Correct |
96 ms |
57080 KB |
Output is correct |
| 7 |
Correct |
126 ms |
77432 KB |
Output is correct |
| 8 |
Correct |
161 ms |
100856 KB |
Output is correct |
| 9 |
Correct |
203 ms |
127480 KB |
Output is correct |
| 10 |
Correct |
247 ms |
157328 KB |
Output is correct |
