Submission #1326471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326471		joacru	Collecting Stamps 3 (JOI20_ho_t3)	C++20	15 / 100	87 ms	32200 KiB

ho_t3

#include <bits/stdc++.h>

#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()

#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)

#define LINE cerr<<"===================================="<<endl

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
	os<<"[";
	forn(i,v.size()){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;
typedef long double ld;

const int INF = 2000000000;

void assign(int &a, int v){
	a = min(a, v);
}

void solve(){
	
	int n, L;
	cin>>n>>L;
	
	vector<int> xs{0};
	forn(i,n){
		int x;
		cin>>x;
		xs.push_back(x);
	}
	xs.push_back(L);
	
	vector<int> ts{0};
	forn(i,n){
		int t;
		cin>>t;
		ts.push_back(t);
	}
	ts.push_back(INF);
	
	n+=2; // inicial y final
	
	int dp[n][n][n];
	
	forn(i,n) forn(j,n) forn(k,n) dp[i][j][k] = INF;
	
	dp[0][0][n-1] = 0;
	
	for(int i = 0; i < n; ++i){ // cantidad de estampas
		for(int j = 1; j < n; ++j){ // tamaño de la ventana
			for(int l = 0; l < n; ++l){ // donde estoy parado
				// recorrido hacia la izquierda
				int r = l - j;
				if(r < 0){
					r=r+n;
					if(r-l > 1){ // todavía hay espacio
						// aumentar el l
						int t = xs[l+1] - xs[l];
						int nt = dp[i][l][r] + t;
						assign(dp[i + bool(nt <= ts[l+1])][l+1][r], nt);
						// reducir el r
						t = L - xs[r-1] + xs[l];
						nt = dp[i][l][r] + t;
						assign(dp[i + bool(nt <= ts[r-1])][r-1][l], nt);
					}
				}
				// recorrido hacia la derecha
				r = l + j;
				if(r >= n){
					r=r-n;
					if(l-r > 1){
						// reducir el l
						int t = xs[l] - xs[l-1];
						int nt = dp[i][l][r] + t;
						assign(dp[i + bool(nt <= ts[l-1])][l-1][r], nt);
						// aumentar el r
						t = L - xs[l] + xs[r+1];
						nt = dp[i][l][r] + t;
						assign(dp[i + bool(nt <= ts[r+1])][r+1][l], nt);
					}
				}
			}
		}
	}
	
	int ans = 0;
	forn(i,n) forn(j,n) forn(k,n) if(dp[i][j][k] < INF) ans = i;
	
	cout<<ans<<"\n";
	
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
		assert(freopen("input.in", "r", stdin));
		//~ freopen("output.out", "w", stdout);
	#endif
	
	#ifdef LOCAL
	int tcs; cin>>tcs;
	while(tcs--)
	#endif
	solve();

	return 0;
}

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