Submission #1263302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263302		pudelos	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	76 ms	131400 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define ll long long
#define eb emplace_back
#define pb push_back
#define pi pair<int, int>
#define f first
#define s second
#define rs resize
#define V vector

const int maxn=203, inf=1e15;
int n, L;
int AS[maxn], AT[maxn], A[maxn];
int BS[maxn], BT[maxn], B[maxn];
int dp[maxn][maxn][2][maxn];

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> L;
  FOR(i, 1, n) cin >> BS[i];
  FOR(i, 1, n) cin >> BT[i];

  FOR(i, 1, n) {
    AS[i]=L-BS[n-i+1];
    AT[i]=BT[n-i+1];
  }

  FOR(i, 1, n) {
    A[i]=AS[i]-AS[i-1];
    B[i]=BS[i]-BS[i-1];
  }

  FOR(a, 0, maxn-1) FOR(b, 0, maxn-1) FOR(c, 0, 1) FOR(k, 0, maxn-1) dp[a][b][c][k]=inf;
  dp[0][0][0][0]=dp[0][0][1][0]=0;
  int odp=0;
  FOR(S, 0, n-1) {
    FOR(a, 0, S) {
      int b = S-a;
      FOR(k, 0, maxn-1) {
        if(dp[a][b][0][k]!=inf) {
          // cout << a << ' ' << b << " 0 " << k << '\n';
          int czas0 = dp[a][b][0][k] + A[a+1];
          int kp0 = k;
          if(czas0<=AT[a+1]) ++kp0;
          dp[a+1][b][0][kp0]=min(dp[a+1][b][0][kp0], czas0);
          odp=max(odp, kp0);

          int czas1 = dp[a][b][0][k] + AS[a] + BS[b+1];
          int kp1 = k;
          if(czas1<=BT[b+1]) ++kp1;
          dp[a][b+1][1][kp1]=min(dp[a][b+1][1][kp1], czas1);
          odp=max(odp, kp1);
        }

        if(dp[a][b][1][k]!=inf) {
          // cout << a << ' ' << b << " 1 " << k << '\n';
          int czas0 = dp[a][b][1][k] + BS[b] + AS[a+1];
          int kp0 = k;
          if(czas0<=AT[a+1]) ++kp0;
          dp[a+1][b][0][kp0]=min(dp[a+1][b][0][kp0], czas0);
          odp=max(odp, kp0);

          int czas1 = dp[a][b][1][k] + B[b+1];
          int kp1 = k;
          if(czas1<=BT[b+1]) ++kp1;
          // if(S==0) cout << czas1 << ' ' << kp1 << '\n';
          dp[a][b+1][1][kp1]=min(dp[a][b+1][1][kp1], czas1);
          odp=max(odp, kp1);
        }
      }
    }
  }

  cout << odp << '\n';
}

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