Submission #1163070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163070		brinton	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	320 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][clockwise/counter_clockwise]
  dp[0][0][0][0] = 0;
  dp[0][0][0][1] = 0;
  for(int cnt = 0;cnt <= N;cnt++){
    for(int a = 0;a <= N;a++){//current at a
      for(int b = 0;b <= N;b++){
        for(int clock = 0;clock <= 1;clock++){
          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;
          return 0;
        }
      }
    }
  }
}

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