oj.uz

Submission #647349

# Submission time Handle Problem Language Result Execution time Memory
647349 2022-10-02T09:38:14 Z beaconmc Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 76 ms 127412 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,l;
ll dp[201][201][201][2];

int main(){
	cin >> n >> l;
	vector<ll> dists(n+1);
	vector<ll> times(n+1);
	FOR(i,1,n+1) cin >> dists[i];
	FOR(i,1,n+1) cin >> times[i];
	FOR(i,0,201){
		FOR(j,0,201){
			FOR(k,0,201){
				dp[i][j][k][0] = 10000000000;
				dp[i][j][k][1] = 10000000000;
			}
		}
	}

	dp[n][0][0][1] = 0;


	// if (times[n] >= l-places[n]) dp[n][1][1][0] = l-places[n];
	// else dp[n][1][0][0] = l-places[n];

	// if (times[1] >= places[1]) dp[n][1][1][1] = places[1];
	// else dp[n][1][0][1] = places[1];

	FOR(k,0,n+1) FORNEG(i,n+1,0) FOR(j,0,n+1){
		if (i<j) continue;


		if (i!=n){
			dp[i][j][k][0] = min(dp[i][j][k][0], dp[i+1][j][k][0] + dists[i+1] - dists[i]);

			if (k!=0){
				ll tm = dists[i+1] - dists[i] + dp[i+1][j][k-1][0];

				if (tm <= times[i]){
					dp[i][j][k][0] = min(dp[i][j][k][0], tm);
				}
			}

			dp[i][j][k][1] = min(dp[i][j][k][1], dp[i+1][j][k][0] + l + dists[j] - dists[i+1]);

			if (k!=0){
				ll tm = dp[i+1][j][k-1][0] + l + dists[j] - dists[i+1];

				if (tm <= times[j]){
					dp[i][j][k][1] = min(dp[i][j][k][1], tm);
				}
			}

		}

		if (j!=0){
			dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j-1][k][1] + dists[j] - dists[j-1]);

			if (k!=0){
				ll tm = dists[j] - dists[j-1] +  dp[i][j-1][k-1][1];

				if (tm <= times[j]){
					dp[i][j][k][1] = min(dp[i][j][k][1], tm);
				}
			}
			dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j-1][k][1] + l + dists[j-1] - dists[i]);

			if (k!=0){
				ll tm = dp[i][j-1][k-1][1] + l + dists[j-1] - dists[i];

				if (tm <= times[i]){
					dp[i][j][k][0] = min(dp[i][j][k][0], tm);
				}
			}

		}

	}


	ll ans = -1;
	FOR(i,0,201) FOR(j,0,201) FOR(k,0,201) FOR(m,0,2){
		if (dp[i][j][k][m] < 10000000000) ans = max(ans, k);
	}
	cout << ans;


}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 127404 KB Output is correct
2 Correct 73 ms 127312 KB Output is correct
3 Correct 76 ms 127412 KB Output is correct
4 Incorrect 63 ms 127408 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 127404 KB Output is correct
2 Correct 73 ms 127312 KB Output is correct
3 Correct 76 ms 127412 KB Output is correct
4 Incorrect 63 ms 127408 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 127404 KB Output is correct
2 Correct 73 ms 127312 KB Output is correct
3 Correct 76 ms 127412 KB Output is correct
4 Incorrect 63 ms 127408 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 127404 KB Output is correct
2 Correct 73 ms 127312 KB Output is correct
3 Correct 76 ms 127412 KB Output is correct
4 Incorrect 63 ms 127408 KB Output isn't correct
5 Halted 0 ms 0 KB -