oj.uz

답안 #201556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201556 2020-02-11T04:37:32 Z abacaba Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 47 ms 78072 KB 
#include <bits/stdc++.h> 
using namespace std;

#define f first
#define se second

template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}

template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int inf = 0x3f3f3f3f;
const int N = 2e2 + 15;
int n, x, dp[2][N][N][N], ans;
pair <int, int> a[N];

// dp[last][l][r][items_taken] = min_time

inline int get(int c, int d) {
	return min({abs(a[c].f - a[d].f), abs(a[c].f + x - a[d].f), abs(a[d].f + x - a[c].f)});
}

inline void calc(int l, int r, int len) {
	// FROM L
	int nxt = (l - 1 + n) % n;
	int d = get(l, nxt);
	if(nxt != r) {
		for(int k = 0; k <= len; ++k) {
			if(dp[0][l][r][k] + d <= a[nxt].se)
				Min(dp[0][nxt][r][k+1], dp[0][l][r][k] + d);
			else
				Min(dp[0][nxt][r][k], dp[0][l][r][k] + d);
		}
	}
	nxt = (r + 1 + n) % n;
	if(nxt != l) {
		d = get(l, nxt);
		for(int k = 0; k <= len; ++k) {
			if(dp[0][l][r][k] + d <= a[nxt].se)
				Min(dp[1][l][nxt][k+1], dp[0][l][r][k] + d);
			else
				Min(dp[1][l][nxt][k], dp[0][l][r][k] + d);
		}
	}

	// FROM R
	nxt = (l - 1 + n) % n;
	if(nxt != r) {
		d = get(r, nxt);
		for(int k = 0; k <= len; ++k) {
			if(dp[1][l][r][k] + d <= a[nxt].se)
				Min(dp[0][nxt][r][k+1], dp[1][l][r][k] + d);
			else
				Min(dp[0][nxt][r][k], dp[1][l][r][k] + d);
		}
	}
	nxt = (r + 1 + n) % n;
	if(nxt != l) {
		d = get(r, nxt);
		for(int k = 0; k <= len; ++k) {
			if(dp[1][l][r][k] + d <= a[nxt].se)
				Min(dp[1][l][nxt][k+1], dp[1][l][r][k] + d);
			else
				Min(dp[1][l][nxt][k], dp[1][l][r][k] + d);
		}
	}
}

main() {
	memset(dp, 0x3f, sizeof(dp));
	freopen("input.txt", "r", stdin);
	cin >> n >> x;
	for(int i = 1; i <= n; ++i)
		cin >> a[i].f;
	for(int i = 1; i <= n; ++i)
		cin >> a[i].se;
	reverse(a + 1, a + 1 + n);
	++n;
	dp[0][0][0][0] = 0;
	for(int len = 0; len < n; ++len) {
		for(int l = 0; l < n; ++l) {
			int r = (l + len - 1) % n;
			calc(l, r, len);
		}
	}
	for(int k = n; k >= 0; --k)
		for(int i = 0; i < 2; ++i)
			for(int l = 0; l < n; ++l)
				for(int r = 0; r < n; ++r)
					if(dp[i][l][r][k] != inf) {
						cout << k << endl;
						return 0;
					}
	return 0;
}

Compilation message

ho_t3.cpp:72:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:74:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.txt", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 78072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 78072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 78072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 78072 KB Output isn't correct
2 Halted 0 ms 0 KB -