Submission #1090378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090378		peacebringer1667	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	114 ms	193872 KiB

ho_t3

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e2 + 5;
const ll inf = 1e16;

template <typename T>
   void minimize(T &x,T y){
   	x = min(x,y);
   }

int dist[maxn][maxn],a[maxn],T[maxn];
ll dp[maxn][maxn][maxn][3];

void prepare(int n,int L){
	//prepare dist
	for (int i = 1 ; i <= n ; i++)
		for (int j = 1 ; j <= n ; j++)
		  dist[i][j] = min(abs(a[i] - a[j]),L - a[i] + a[j]);
    
    for (int i = 1 ; i <= n ; i++) 
	   for (int j = 1 ; j <= n ; j++) 
	      for (int k = 0 ; k <= n ; k++)
            dp[i][j][k][0] = dp[i][j][k][1] = inf;
            
    for (int i = 1 ; i <= n ; i++){
      if (min(a[i],L - a[i]) <= T[i]) dp[i][i][1][0] = dp[i][i][1][1] = min(a[i],L - a[i]);
      dp[i][i][0][0] = dp[i][i][0][1] = min(a[i],L - a[i]);
    }
    
}

int solve(int n){
	int res = 0;
    for (int len = 1 ; len < n ; len++)
    	for (int l = 1 ; l <= n ; l++){
    		int r = l + len;
    		if (r > n) r -= n;
    		
    		int lx = (l == n) ? 1 : (l + 1);
    		int rx = (r == 1) ? n : (r - 1);
    		
    		for (int k = 1 ; k <= len + 1; k++){
			    minimize(dp[l][r][k][0],dp[lx][r][k][0] + dist[l][lx]);
			    minimize(dp[l][r][k][0],dp[lx][r][k][1] + dist[l][r]);
				
				minimize(dp[l][r][k][1],dp[l][rx][k][1] + dist[rx][r]);
				minimize(dp[l][r][k][1],dp[l][rx][k][0] + dist[l][r]);
				
				if (dp[lx][r][k - 1][0] + dist[l][lx] <= T[l])
				  minimize(dp[l][r][k][0],dp[lx][r][k - 1][0] + dist[l][lx]);
				if (dp[lx][r][k - 1][1] + dist[l][r] <= T[l])
				  minimize(dp[l][r][k][0],dp[lx][r][k - 1][1] + dist[l][r]);
				
				
				if (dp[l][rx][k - 1][1] + dist[rx][r] <= T[r])
				  minimize(dp[l][r][k][1],dp[l][rx][k - 1][1] + dist[rx][r]);
				if (dp[l][rx][k - 1][0] + dist[l][r] <= T[r])
				  minimize(dp[l][r][k][1],dp[l][rx][k - 1][0] + dist[l][r]);
			}
		}
	
	for (int l = 1 ; l <= n ; l++)
	  for (int r = 1 ; r <= n ;r++)
	    for (int k = 1 ; k <= n ; k++)
	      if (min(dp[l][r][k][0],dp[l][r][k][1]) < inf)
	      	res = max(res,k);
	      
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,L;
	cin >> n >> L;
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	for (int i = 1 ; i <= n ; i++) cin >> T[i];
	
	prepare(n,L);
	
	cout << solve(n);
    
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int solve(int)':
ho_t3.cpp:41:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |     for (int len = 1 ; len < n ; len++)
      |     ^~~
ho_t3.cpp:69:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |  for (int l = 1 ; l <= n ; l++)
      |  ^~~

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