Submission #208938

#	Time	Username	Problem	Language	Result	Execution time	Memory
208938		eriksuenderhauf	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	159 ms	135416 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e2 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int X[N], T[N], n, l, ans = 0;
ll dp[N][N][N][2];

ll dist(int i, int j) { return min(abs(X[i]-X[j]), l - abs(X[i]-X[j])); }
void ckmn(ll& x, ll y) { x = min(x, y); }

int main() {
  scanf("%d %d", &n, &l);
  for (int i = 1; i <= n; i++) scanf("%d", X+i);
  for (int i = 1; i <= n; i++) scanf("%d", T+i);
  memset(dp, 0x3f, sizeof dp);
  dp[0][0][0][0] = dp[0][0][0][1] = 0;
  for (int i = 0; i < n; i++) {
    for (int r = 0, l = i; r <= i; r++, l--) {
      ll v;
      for (int k = 0; k <= i; k++) {
        v = dp[l][r][k][0] + dist(n+1-l, n-l);
        ckmn(dp[l+1][r][k + (v <= T[n-l])][0], v);
        v = dp[l][r][k][0] + dist(n+1-l, r+1);
        ckmn(dp[l][r+1][k + (v <= T[r+1])][1], v);
        v = dp[l][r][k][1] + dist(r, n-l);
        ckmn(dp[l+1][r][k + (v <= T[n-l])][0], v);
        v = dp[l][r][k][1] + dist(r, r+1);
        ckmn(dp[l][r+1][k + (v <= T[r+1])][1], v);
      }
    }
  }
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++)
        for (int f = 0; f < 2; f++)
          if (dp[i][j][k][f] != inf)
            ans = max(ans, k);
  printf("%d\n", ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &l);
   ~~~~~^~~~~~~~~~~~~~~~~
ho_t3.cpp:14:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; i++) scanf("%d", X+i);
                                ~~~~~^~~~~~~~~~~
ho_t3.cpp:15:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int i = 1; i <= n; i++) scanf("%d", T+i);
                                ~~~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75