oj.uz

Submission #56553

# Submission time Handle Problem Language Result Execution time Memory
56553 2018-07-11T16:47:02 Z Bruteforceman Pinball (JOI14_pinball) C++11
51 / 100
 1000 ms 22240 KB 
#include <bits/stdc++.h>
using namespace std;
int M, N;
int a[100010], b[100010], c[100010];
int cost[100010];
long long pre[100010];
long long suf[100010];
const long long inf = 1e18;
long long t[500010 * 4];
int idx;

long long query(int x, int y, int c = 1, int b = 1, int e = idx) {
	if(x <= b && e <= y) {
		return t[c];
	}
	if(y < b || e < x) return inf;
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	return min(query(x, y, l, b, m), query(x, y, r, m+1, e));
}
void update(int x, long long val, int c = 1, int b = 1, int e = idx) {
	if(b == e) {
		t[c] = min(t[c], val);
		return ;
	} 
	int m = (b + e) >> 1;
	int l = c << 1;
	int r = l + 1;
	if(x <= m) update(x, val, l, b, m); 
	else update(x, val, r, m+1, e);
	t[c] = min(t[l], t[r]);
}

int main(int argc, char const *argv[])
{
	map <int, int> com;
	scanf("%d %d", &M, &N);

	com[1]; com[N];
	for(int i = 1; i <= M; i++) {
		scanf("%d %d %d %d", &a[i], &b[i], &c[i], &cost[i]);
		if(a[i] > 1) com[a[i] - 1];
		com[a[i]];
		if(b[i] < N) com[b[i] + 1];
		com[b[i]];
		com[c[i]];
	}
	idx = 0;
	for(auto &i : com) {
		i.second = ++idx;
	}
	for(int i = 1; i <= M; i++) {
		a[i] = com[a[i]];
		b[i] = com[b[i]];
		c[i] = com[c[i]];
	}
	int start = com[1];
	int end = com[N];
	for(int i = 0; i <= 4 * idx; i++) {
		t[i] = inf;
	}
	for(int i = 1; i <= M; i++) {
		if(a[i] == start) {
			pre[i] = cost[i];
		} else {
			pre[i] = inf;
		}
		pre[i] = min(pre[i], query(a[i], b[i]) + cost[i]);
		update(c[i], pre[i]);
	}
	for(int i = 0; i <= 4 * idx; i++) {
		t[i] = inf;
	}
	for(int i = 1; i <= M; i++) {
		if(b[i] == end) {
			suf[i] = cost[i];
		} else {
			suf[i] = inf;
		}
		suf[i] = min(suf[i], query(a[i], b[i]) + cost[i]);
		update(c[i], suf[i]);
	}
	long long ans = inf;
	for(int i = 1; i <= M; i++) {
		ans = min(ans, pre[i] + suf[i] - cost[i]);
	}
	if(ans > (inf / 3)) {
		ans = -1;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

pinball.cpp: In function 'int main(int, const char**)':
pinball.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &M, &N);
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a[i], &b[i], &c[i], &cost[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 2 ms 612 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 1 ms 676 KB Output is correct
12 Correct 3 ms 676 KB Output is correct
13 Correct 4 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 1 ms 676 KB Output is correct
12 Correct 3 ms 676 KB Output is correct
13 Correct 4 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 3 ms 676 KB Output is correct
17 Correct 6 ms 704 KB Output is correct
18 Correct 5 ms 704 KB Output is correct
19 Correct 7 ms 1004 KB Output is correct
20 Correct 5 ms 1004 KB Output is correct
21 Correct 4 ms 1004 KB Output is correct
22 Correct 5 ms 1004 KB Output is correct
23 Correct 5 ms 1004 KB Output is correct
24 Correct 6 ms 1004 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 484 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 2 ms 612 KB Output is correct
9 Correct 3 ms 612 KB Output is correct
10 Correct 3 ms 676 KB Output is correct
11 Correct 1 ms 676 KB Output is correct
12 Correct 3 ms 676 KB Output is correct
13 Correct 4 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 3 ms 676 KB Output is correct
17 Correct 6 ms 704 KB Output is correct
18 Correct 5 ms 704 KB Output is correct
19 Correct 7 ms 1004 KB Output is correct
20 Correct 5 ms 1004 KB Output is correct
21 Correct 4 ms 1004 KB Output is correct
22 Correct 5 ms 1004 KB Output is correct
23 Correct 5 ms 1004 KB Output is correct
24 Correct 6 ms 1004 KB Output is correct
25 Correct 80 ms 2800 KB Output is correct
26 Correct 169 ms 8020 KB Output is correct
27 Correct 578 ms 13548 KB Output is correct
28 Correct 278 ms 13548 KB Output is correct
29 Correct 388 ms 13548 KB Output is correct
30 Correct 307 ms 13548 KB Output is correct
31 Execution timed out 1053 ms 22240 KB Time limit exceeded
32 Halted 0 ms 0 KB -