oj.uz

Submission #44514

# Submission time Handle Problem Language Result Execution time Memory
44514 2018-04-02T18:35:09 Z KieranHorgan Go (COCI18_go) C++17
70 / 100
 291 ms 260056 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 259704 KB Output is correct
2 Correct 183 ms 259716 KB Output is correct
3 Correct 181 ms 259744 KB Output is correct
4 Correct 184 ms 259772 KB Output is correct
5 Incorrect 197 ms 259904 KB Output isn't correct
6 Incorrect 205 ms 259908 KB Output isn't correct
7 Incorrect 240 ms 259932 KB Output isn't correct
8 Correct 291 ms 260056 KB Output is correct
9 Correct 277 ms 260056 KB Output is correct
10 Correct 274 ms 260056 KB Output is correct