Submission #456430

#	Time	Username	Problem	Language	Result	Execution time	Memory
456430		ntabc05101	Go (COCI18_go)	C++14	100 / 100	235 ms	173380 KiB

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 / 100