Submission #208936

#	Time	Username	Problem	Language	Result	Execution time	Memory
208936		eriksuenderhauf	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	162 ms	135444 KiB

ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(x, a) for (const auto& x: a)
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N = 2e2 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int X[N], T[N];
ll dp[N][N][N][2];
int n, l;

ll dist(int i, int j) {
  return min(abs(X[i]-X[j]), l - abs(X[i]-X[j]));
}

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);
  int ans = 0;
  dp[0][0][0][0] = dp[0][0][0][1] = 0;
  for (int i = 0; i < n; i++) {
    for (int r = 0; r <= i; r++) {
      int l = i-r, fl;
      for (int k = 0; k <= i; k++) {
        fl = dp[l][r][k][0] + dist(n+1-l, n+1-(l+1)) <= T[n+1-(l+1)];
        dp[l+1][r][k+fl][0] = min(dp[l+1][r][k+fl][0], dp[l][r][k][0] + dist(n+1-l, n+1-(l+1)));
        fl = dp[l][r][k][0] + dist(n+1-l, r+1) <= T[r+1];
        dp[l][r+1][k+fl][1] = min(dp[l][r+1][k+fl][1], dp[l][r][k][0] + dist(n+1-l, r+1));

        fl = dp[l][r][k][1] + dist(r, n+1-(l+1)) <= T[n+1-(l+1)];
        dp[l+1][r][k+fl][0] = min(dp[l+1][r][k+fl][0], dp[l][r][k][1] + dist(r, n+1-(l+1)));
        fl = dp[l][r][k][1] + dist(r, r+1) <= T[r+1];
        dp[l][r+1][k+fl][1] = min(dp[l][r+1][k+fl][1], dp[l][r][k][1] + dist(r, r+1));
      }
    }
  }
  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:21: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:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", X+i);
     ~~~~~^~~~~~~~~~~
ho_t3.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", T+i);
     ~~~~~^~~~~~~~~~~

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