제출 #1142606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142606		nuutsnoynton	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	1506 ms	128828 KiB

ho_t3

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll a[202], b[202], cost_baruun[202], cost_zuun[202];
ll baruun[202][202][202], ans, zuun[202][202][202], N;
int main() {
	ll n, m, r, x, y, i, lenght, cnt1, s, lef, rig, cnt, j, t;
	N = n;
	cin >> n >> m;
	
	a[0] = 0;
	for (i = 1; i <= n; i ++) cin >> a[i];
	for (i = 1; i < n + 1; i ++) {
		b[n + 1 - i] =m- a[i];
	}
	b[0]= 0;
	for (i = 1; i <= n; i ++) cin >> cost_baruun[i];
	for (i = 1; i <= n; i ++) cost_zuun[i] = cost_baruun[n  + 1 - i];
	ans = 0;
	for (i = 0; i <= 200; i ++) for (j = 0; j <= 200; j++) for ( r = 0; r <= 200; r ++) baruun[i][j][r] = zuun[i][j][r] =1e18; 
	baruun[0][0][0] = zuun[0][0][0] = 0;
	for ( lenght = 1; lenght <= n; lenght ++){
		for ( lef = 0; lef <= n; lef ++) {
			for ( rig = 0; lef + rig <= lenght; rig ++) {
				for ( cnt = 0; cnt <= n; cnt ++) {
					// baruun
					if ( baruun[lef][rig][cnt] != 1e18) ans = max(ans, cnt);
					if ( zuun[lef][rig][cnt] != 1e18) ans = max(ans, cnt);
					if ( rig < n) {
						s = baruun[lef][rig][cnt] + (a[rig + 1] - a[rig]);
						cnt1 = cnt;
						if ( s <= cost_baruun[rig + 1]) cnt1 ++;
						baruun[lef][rig + 1][cnt1] = min(baruun[lef][rig + 1][cnt1], s);
						s = zuun[lef][rig][cnt] + (b[lef] + a[rig + 1]);
						cnt1 = cnt;
						if ( s <= cost_baruun[rig + 1]) cnt1 ++;
						baruun[lef][rig + 1][cnt1] = min(baruun[lef][rig + 1][cnt1], s);
					}
					if ( lef < n) {
						s = baruun[lef][rig][cnt] + (a[rig] + b[lef + 1]);
						cnt1 = cnt;
						if ( s <= cost_zuun[lef + 1]) cnt1 ++;
						zuun[lef + 1][rig][cnt1] = min(zuun[lef + 1][rig][cnt1], s);
						s = zuun[lef][rig][cnt] + (b[lef + 1] - b[lef]);
						cnt1 = cnt;
						if ( s <= cost_zuun[lef + 1]) cnt1 ++;
						zuun[lef + 1][rig][cnt1] = min(zuun[lef + 1][rig][cnt1], s);
					}
					
				}
			}
		}
	}
	
	cout << ans << endl;
}

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