Submission #1163141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163141		brinton	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	574 ms	448904 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (long long)(1e15)
signed main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  //start here
  int N,L;
  cin >> N >> L;
  vector<int> X(N+1,0);
  vector<int> T(N+1,0);
  for(int i = 1;i <= N;i++)cin >> X[i];
  for(int i = 1;i <= N;i++)cin >> T[i];
  vector dp(N+1,vector(N+1,vector(N+1,vector<int>(2,inf))));// dp[a][b][cnt][counter_clockwise/clockwise]
  dp[0][0][0][0] = 0;
  dp[0][0][0][1] = 0;
  for(int len = 1;len <= N;len++){
    for(int a = 0;a <= N;a++){//current at a
      for(int cnt = 0;cnt <= N;cnt++){
        for(int clock = 0;clock <= 1;clock++){
          int b;
          if(clock == 1){
            b = (a+(len-1))%(N+1);
          }else{
            b = (a-(len-1)+N+1)%(N+1);
          }
          if(dp[a][b][cnt][clock] == inf)continue;
          int ctime = dp[a][b][cnt][clock];
          
          
          // go to a-1
          if(clock){// clockwise(1)
            int nxtA = (a-1+N+1)%(N+1);
            int nxtB = (b+1)%(N+1);
            if(nxtA == b)continue;
            {
              int ntime = ctime+min(abs(X[nxtA]-X[a]),L-abs(X[nxtA]-X[a]));
              dp[nxtA][b][cnt+(ntime <= T[nxtA])][1] = 
              min(dp[nxtA][b][cnt+(ntime <= T[nxtA])][1],ntime);
            }
            // go to other+1
            {
              int ntime = ctime+min(abs(X[nxtB]-X[a]),L-abs(X[nxtB]-X[a]));
              dp[nxtB][a][cnt+(ntime <= T[nxtB])][0] = 
              min(dp[nxtB][a][cnt+(ntime <= T[nxtB])][0],ntime);
            }
          }else{//counter clockwise
            int nxtA = (a+1)%(N+1);
            int nxtB = (b-1+N+1)%(N+1);
            if(nxtA == b)continue;
            // go to nxtA
            {
              int ntime = ctime+min(abs(X[nxtA]-X[a]),L-abs(X[nxtA]-X[a]));
              dp[nxtA][b][cnt+(ntime <= T[nxtA])][0] = 
              min(dp[nxtA][b][cnt+(ntime <= T[nxtA])][0],ntime);
            }
            // go to nxtB
            {
              int ntime = ctime+min(abs(X[nxtB]-X[a]),L-abs(X[nxtB]-X[a]));
              dp[nxtB][a][cnt+(ntime <= T[nxtB])][1] = 
              min(dp[nxtB][a][cnt+(ntime <= T[nxtB])][1],ntime);
            }
          }
        }
      }
    }
  }

  for(int cnt = N;cnt >= 0;cnt--){
    for(int a = 0;a <= N;a++){
      for(int b = 0;b <= N;b++){
        for(int clock = 0;clock <= 1;clock++){
          if(dp[a][b][cnt][clock] == inf)continue;
          cout << cnt << '\n';
          return 0;
        }
      }
    }
  }
}

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