제출 #1222456

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

ho_t3

#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 205;
int n, l;
int t[N], p[N];
int dp[N][N][N][2];

int dist(int x, int y) {
	if(x <= y){
		assert(p[y] - p[x] >= 0);
		return p[y] - p[x];
	}
	assert(l - p[x] + p[y] >= 0);
	return l - p[x] + p[y];
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> l;
	p[n + 1] = l;
	for(int i = 1; i <= n; i++) cin >> p[i];
	for(int i = 1; i <= n; i++) cin >> t[i];
	memset(dp, 0x3f, sizeof dp);
	dp[0][0][n + 1][0] = dp[0][0][n + 1][1] = 0;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= n; j++) {
			for(int k = n + 1; k > j; k--) {
				if(j + (n + 1) - k < i) continue;
				if(i > 0) {
					if(j > 0) {
						if(dp[i - 1][j - 1][k][1] + dist(j - 1, j) <= t[j]) {
							dp[i][j][k][1] = min(dp[i][j][k][1], dp[i - 1][j - 1][k][1] + dist(j - 1, j));
						}
						if(dp[i - 1][j - 1][k][0] + dist(k, j) <= t[j]) {
							dp[i][j][k][1] = min(dp[i][j][k][1], dp[i - 1][j - 1][k][0] + dist(k, j));
						}
					}
					if(k <= n) {
						if(dp[i - 1][j][k + 1][0] + dist(k, k + 1) <= t[k]) {
							dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k + 1][0] + dist(k, k + 1));
						}
						if(dp[i - 1][j][k + 1][1] + dist(k, j) <= t[k]) {
							dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k + 1][1] + dist(k, j));
						}
					}
				}
				if(j > 0) {
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j - 1][k][1] + dist(j - 1, j));
					dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j - 1][k][0] + dist(k, j));
				}
				if(k <= n) {
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j][k + 1][0] + dist(k, k + 1));
					dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j][k + 1][1] + dist(k, j));
				}
			}
		}
	}
	for(int ans = n; ans >= 0; ans--) {
		for(int i = 0; i <= n; i++) {
			for(int j = n + 1; j > i; j--) {
				if(dp[ans][i][j][0] < 1e15 or dp[ans][i][j][1] < 1e15) {
					cout << ans << ln;
					return 0;
				}
			}
		}
	}
	cout << 0 << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:32:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:33:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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