Submission #224026

#	Time	Username	Problem	Language	Result	Execution time	Memory
224026		shenxy	Collecting Stamps 3 (JOI20_ho_t3)	C++11	0 / 100	5 ms	384 KiB

ho_t3

#include <cstdio>
#include <algorithm>
#include <queue>
#include <functional>
#include <vector>
#define F first
#define S second
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> state;
typedef pair<int, state> val;
const int INF = 2000000000;
int N, L, X[202], T[202], dist[202][202][2];
int main() {
	scanf("%d %d", &N, &L);
	for (int i = 1; i <= N; ++i) scanf("%d", &X[i]);
	for (int i = 1; i <= N; ++i) scanf("%d", &T[i]);
	X[0] = 0;
	X[N + 1] = L;
	for (int i = 0; i < N + 2; ++i) {
		for (int j = 0; j < N + 2; ++j) dist[i][j][0] = dist[i][j][1] = INF;
	}
	priority_queue< val, vector<val>, greater<val> > pq;
	pq.push(val(0, state(ii(0, N + 1), 0)));
	pq.push(val(0, state(ii(0, N + 1), 1)));
	dist[0][N + 1][0] = dist[0][N + 1][1] = 0;
	while (!pq.empty()) {
		val v = pq.top();
		pq.pop();
		if (v.F > dist[v.S.F.F][v.S.F.S][v.S.S]) continue;
		if (v.S.F.S - v.S.F.F == 1) continue;
		if (v.S.S) {
			if (dist[v.S.F.F][v.S.F.S][1] + X[v.S.F.F + 1] - X[v.S.F.F] <= T[v.S.F.F + 1]) {
				dist[v.S.F.F + 1][v.S.F.S][1] = dist[v.S.F.F][v.S.F.S][1] + X[v.S.F.F + 1] - X[v.S.F.F];
				pq.push(val(dist[v.S.F.F + 1][v.S.F.S][1], state(ii(v.S.F.F + 1, v.S.F.S), 1)));
			}
			if (dist[v.S.F.F][v.S.F.S][1] + L - X[v.S.F.S - 1] + X[v.S.F.F] <= T[v.S.F.S - 1]) {
				dist[v.S.F.F][v.S.F.S - 1][1] = dist[v.S.F.F][v.S.F.S][1] + L - X[v.S.F.S - 1] + X[v.S.F.F];
				pq.push(val(dist[v.S.F.F][v.S.F.S - 1][1], state(ii(v.S.F.F, v.S.F.S - 1), 1)));
			}
		} else {
			if (dist[v.S.F.F][v.S.F.S][0] + X[v.S.F.S] - X[v.S.F.S - 1] <= T[v.S.F.S - 1]) {
				dist[v.S.F.F][v.S.F.S - 1][0] = dist[v.S.F.F][v.S.F.S][0] + X[v.S.F.S] - X[v.S.F.S - 1];
				pq.push(val(dist[v.S.F.F][v.S.F.S - 1][0], state(ii(v.S.F.F, v.S.F.S - 1), 0)));
			}
			if (dist[v.S.F.F][v.S.F.S][0] + L - X[v.S.F.S] + X[v.S.F.F + 1] <= T[v.S.F.F + 1]) {
				dist[v.S.F.F + 1][v.S.F.S][0] = dist[v.S.F.F][v.S.F.S][1] + L - X[v.S.F.S] + X[v.S.F.F + 1];
				pq.push(val(dist[v.S.F.F + 1][v.S.F.S][0], state(ii(v.S.F.F + 1, v.S.F.S), 0)));
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= N; ++i) {
		for (int j = i + 1; j < N + 2; ++j) {
			if (dist[i][j][0] != INF || dist[i][j][1] != INF) ans = max(ans, N - j + i + 1);
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~~
ho_t3.cpp:16:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; ++i) scanf("%d", &X[i]);
                               ~~~~~^~~~~~~~~~~~~
ho_t3.cpp:17:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; ++i) scanf("%d", &T[i]);
                               ~~~~~^~~~~~~~~~~~~

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