oj.uz

Submission #224026

# Submission time Handle Problem Language Result Execution time Memory
224026 2020-04-17T05:17:30 Z shenxy Collecting Stamps 3 (JOI20_ho_t3) C++11
0 / 100
 5 ms 384 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -