Submission #206660

#	Time	Username	Problem	Language	Result	Execution time	Memory
206660		davitmarg	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	170 ms	65912 KiB

ho_t3

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 205;

int n, L, x[N], t[N], ans;
int dp[N][N][N][2];

int sf(int x)
{
	return n - x + 1;
}

int main()
{
	cin >> n >> L;
	for (int i = 1; i <= n; i++)
		cin >> x[i];
	for (int i = 1; i <= n; i++)
		cin >> t[i];

	for (int s = 0; s <= n; s++)
		for (int p = 0; p <= n; p++)
			for (int i = 0; i <= n; i++)
				dp[p][s][i][0] = dp[p][s][i][1] = mod;

	dp[0][0][0][1] = dp[0][0][0][0] = 0;
	x[n + 1] = L;
	for (int c = 0; c < n; c++)
		for (int p = 0; p <= c; p++)
			for (int C = 0; C < n; C++)
			{
				int s = c - p;

				int T;

				//left
				T = dp[p][s][C][0];
				dp[p + 1][s][C + (T + x[p + 1] - x[p] <= t[p + 1])][0] = min(dp[p + 1][s][C + (T + x[p + 1] - x[p] <= t[p + 1])][0],T + x[p + 1] - x[p]);
				dp[p][s + 1][C + (T + x[p] + L - x[sf(s + 1)] <= t[sf(s + 1)])][1] = min(dp[p][s + 1][C + (T + x[p] + L - x[sf(s + 1)] <= t[sf(s + 1)])][1],T + x[p] + L - x[sf(s + 1)]);


				//right
				T = dp[p][s][C][1];
				dp[p][s + 1][C + (T + x[sf(s)] - x[sf(s + 1)] <= t[sf(s + 1)])][1] = min(dp[p][s + 1][C + (T + x[sf(s)] - x[sf(s + 1)] <= t[sf(s + 1)])][1], T + x[sf(s)] - x[sf(s + 1)]);
				dp[p + 1][s][C + (T + x[p + 1] + L - x[sf(s)] <= t[p + 1])][0] = min(dp[p + 1][s][C + (T + x[p + 1] + L - x[sf(s)] <= t[p + 1])][0], T + x[p + 1] + L - x[sf(s)]);
			}

	for (int c = 0; c <= n; c++)
		for (int p = 0; p <= n; p++)
			for (int s = 0; s <= n; s++)
				for (int d = 0; d <= 1; d++)
					if (dp[p][s][c][d] != mod)
						ans = c;

	cout << ans << endl;
	return 0;
}

/*

5
1 2 3 4 5
5 4 3 2 1


*/

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