Submission #456430

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
456430	2021-08-06T17:26:49 Z	ntabc05101	Go (COCI18_go)	C++14	100 / 100	235 ms	173380 KB

go

#include <bits/stdc++.h>
using namespace std;

int n, m, k, p[105], w[105], e[105], mem[105][105][2][2005];

int dp(int l, int r, int E, int t) {
  if (l < 1 || r > m)
    return 0;
  int &ret = mem[l][r][E][t];
  if (~ret)
    return ret;

  ret = 0;
  if (!E) {
    ret = max(ret, dp(l - 1, r, 0, min(2001, abs(p[l] - p[l - 1]) + t)) + (t < e[l] ? w[l] : 0));
    ret = max(ret, dp(l, r + 1, 1, min(2001, abs(p[l] - p[r + 1]) + t)) + (t < e[l] ? w[l] : 0));
  }
  else {
    ret = max(ret, dp(l - 1, r, 0, min(2001, abs(p[r] - p[l - 1]) + t)) + (t < e[r] ? w[r] : 0));
    ret = max(ret, dp(l, r + 1, 1, min(2001, abs(p[r] - p[r + 1]) + t)) + (t < e[r] ? w[r] : 0));
  }
  return ret;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k >> m;
  for (int i = 1; i <= m; i++) {
    cin >> p[i] >> w[i] >> e[i];
  }
  p[m + 1] = n + 100;
  memset(mem, -1, sizeof mem);
  int ans = 0;
  for (int i = 1; i <= m; i++) {
    ans = max(ans, dp(i, i, 0, abs(p[i] - k)));
  }

  cout << ans << endl;

  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	173332 KB	Output is correct
2	Correct	74 ms	173232 KB	Output is correct
3	Correct	76 ms	173300 KB	Output is correct
4	Correct	74 ms	173300 KB	Output is correct
5	Correct	105 ms	173224 KB	Output is correct
6	Correct	102 ms	173320 KB	Output is correct
7	Correct	155 ms	173316 KB	Output is correct
8	Correct	182 ms	173380 KB	Output is correct
9	Correct	199 ms	173284 KB	Output is correct
10	Correct	235 ms	173336 KB	Output is correct