제출 #1336104

#제출 시각아이디문제언어결과실행 시간메모리
1336104blackscreen1Collecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
98 ms130868 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, t1;
pll a[205];
ll dp[205][205][205][2];
inline ll ev(ll x, ll y) {
	return min(abs(x-y), m - abs(x-y));
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	iloop(0, n) cin >> a[i].first;
	iloop(0, n) cin >> a[i].second;
	iloop(0, n+1) jloop(0, n+1) kloop(0, n+1) lloop(0, 2) dp[i][j][k][l] = INF;
	iloop(0, n) {
		dp[0][i+1][0][0] = dp[0][0][n-i][1] = min(a[i].first, m - a[i].first);
		if (ev(0, a[i].first) <= a[i].second) dp[1][i+1][0][0] = dp[1][0][n-i][1] = min(a[i].first, m - a[i].first);
	}
	iloop(1, n+1) jloop(0, n+1) kloop(0, n+1) {
		if (j + k < i || j + k > n) continue;
		if (j) {
			dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j-1][k][0] + ev(a[j-1].first, (j > 1 ? a[j-2].first : a[n-1].first)));
			if (dp[i-1][j-1][k][0] + ev(a[j-1].first, (j > 1 ? a[j-2].first : a[n-1].first)) <= a[j-1].second) {
				dp[i][j][k][0] = min(dp[i][j][k][0], dp[i-1][j-1][k][0] + ev(a[j-1].first, (j > 1 ? a[j-2].first : a[n-1].first)));
			}
			if (k) {
				dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j][k-1][0] + ev(a[n-k].first, a[j-1].first));
				if (dp[i-1][j][k-1][0] + ev(a[n-k].first, a[j-1].first) <= a[n-k].second) {
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i-1][j][k-1][0] + ev(a[n-k].first, a[j-1].first));
				}
			}
		}
		if (k) {
			dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j][k-1][1] + ev(a[n-k].first, (k > 1 ? a[n-k+1].first : a[0].first)));
			if (dp[i-1][j][k-1][1] + ev(a[n-k].first, (k > 1 ? a[n-k+1].first : a[0].first)) <= a[n-k].second) {
				dp[i][j][k][1] = min(dp[i][j][k][1], dp[i-1][j][k-1][1] + ev(a[n-k].first, (k > 1 ? a[n-k+1].first : a[0].first)));
			}
			if (j) {
				dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j-1][k][1] + ev(a[n-k].first, a[j-1].first));
				if (dp[i-1][j-1][k][1] + ev(a[n-k].first, a[j-1].first) <= a[j-1].second) {
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i-1][j-1][k][1] + ev(a[n-k].first, a[j-1].first));
				}
			}
		}
	}
	//iloop(1, n+1) jloop(0, n+1) kloop(0, n+1) cout << i << "," << j << "," << k << ":" << dp[i][j][k][0] << " " << dp[i][j][k][1] << endl;
	iloop(n, -1) jloop(0, n+1) kloop(0, n+1) if (min(dp[i][j][k][0], dp[i][j][k][1]) < INF) {cout << i; return 0;}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...