제출 #44514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44514		KieranHorgan	Go (COCI18_go)	C++17	70 / 100	291 ms	260056 KiB

go

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())
const int INF = 1000000000;
const int MOD = 1000000007;
const int MAXN = 100;

int n, k, m;
int a[1005];
int b[1005];
int lt[1005];
int dp[3005][105][105];

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  memset(dp, -1, sizeof(dp));
  cin >> n >> k >> m;
  for(int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i] >> lt[i];
    dp[1+abs(k-a[i])][i][i] = (abs(k-a[i])<=lt[i]?b[i]:-1);
  }
  int ans = 0;
  for(int t = 0; t <= 2000; t++) {
    for(int cur = 1; cur <= m; cur++) {
      for(int far = 1; far <= m; far++) {
        if(dp[t][cur][far]==-1) continue;
        ans = max(ans, dp[t][cur][far]);

        if(a[cur] <= k && far >= cur) {
          if(cur != 1) {
            dp[t+(abs(a[cur]-a[cur-1]))][cur-1][far] = max(dp[t+(abs(a[cur]-a[cur-1]))][cur-1][far], dp[t][cur][far] + (t+(abs(a[cur]-a[cur-1])) <= lt[cur-1]?b[cur-1]:0));
          }
          if(far != m) {
            dp[t+(abs(a[cur]-a[far+1]))][far+1][cur] = max(dp[t+(abs(a[cur]-a[far+1]))][far+1][cur], dp[t][cur][far] + (t+(abs(a[cur]-a[far+1])) <= lt[far+1]?b[far+1]:0));
          }
        }
        if(a[cur] >= k && far <= cur) {
          if(cur != m) {
              dp[t+(abs(a[cur]-a[cur+1]))][cur+1][far] = max(dp[t+(abs(a[cur]-a[cur+1]))][cur+1][far], dp[t][cur][far] + (t+(abs(a[cur]-a[cur+1])) <= lt[cur+1]?b[cur+1]:0));
          }
          if(far != 1) {
            dp[t+(abs(a[cur]-a[far-1]))][far-1][cur] = max(dp[t+(abs(a[cur]-a[far-1]))][far-1][cur], dp[t][cur][far] + (t+(abs(a[cur]-a[far-1])) <= lt[far-1]?b[far-1]:0));
          }
        }
      }
    }
  }
  cout << ans << endl;
}

• Subtask 1: 70 / 100