Submission #318619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
318619	2020-11-02T14:03:08 Z	MetB	Safety (NOI18_safety)	C++14	22 / 100	2000 ms	262148 KB

safety

#include <bits/stdc++.h>
 
#define N 2000001
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
 
const ll INF = 1e18, MOD = 998244353, MOD2 = 1e6 + 3;

ll d[2][501*1000], a[500], n, h;
vector <ll> srt;

struct window : deque < pair <ll, ll> > {
	void append (ll x, ll v) {
		while (!empty () && back ().second > v) pop_back ();
		emplace_back (x, v);
	}

	void erase (ll x) {
		if (front().first == x) pop_front ();
	}
};

int main () {
	cin >> n >> h;

	for (int i = 0; i < n; i++) {
		cin >> a[i];

		srt.push_back (a[i]);

		for (int j = 1; j <= n; j++) {
			srt.push_back (a[i] + j * h);
			srt.push_back (a[i] - j * h);
		}
	}

	sort (srt.begin(), srt.end());
	srt.erase (unique (srt.begin(), srt.end()), srt.end ());

	int sz = srt.size ();

	for (int i = 0; i < sz; i++) {
		d[0][i] = abs (srt[i] - a[0]);
		//cout << d[0][i] << ' ' << srt[i] << endl;
	}

	for (int i = 1; i < n; i++) {
		int k = i % 2;
		int l = 0, r = 0;
		window wd;
		for (int j = 0; j < sz; j++) {
			while (r < sz && srt[r] <= srt[j] + h) { wd.append (r, d[!k][r]); r++; };
			while (l < r && srt[l] < srt[j] - h) { wd.erase (l); l++; };
			d[k][j] = abs (srt[j] - a[i]) + wd.front ().second;
			//cout << i << ' ' << srt[j] << ' ' << srt[l] << ' ' << srt[r-1] << ' ' << *ms.begin () << endl; 
		}
	}

	cout << *min_element (d[(n-1)%2], d[(n-1)%2] + sz);
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	276 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	90 ms	4680 KB	Output is correct
14	Correct	18 ms	4572 KB	Output is correct
15	Correct	1392 ms	8392 KB	Output is correct
16	Correct	38 ms	4572 KB	Output is correct
17	Correct	1107 ms	7304 KB	Output is correct
18	Correct	530 ms	4696 KB	Output is correct
19	Correct	31 ms	4572 KB	Output is correct

Subtask #6
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	90 ms	4680 KB	Output is correct
14	Correct	18 ms	4572 KB	Output is correct
15	Correct	1392 ms	8392 KB	Output is correct
16	Correct	38 ms	4572 KB	Output is correct
17	Correct	1107 ms	7304 KB	Output is correct
18	Correct	530 ms	4696 KB	Output is correct
19	Correct	31 ms	4572 KB	Output is correct
20	Correct	1993 ms	10184 KB	Output is correct
21	Execution timed out	2012 ms	10444 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #7
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	90 ms	4680 KB	Output is correct
14	Correct	18 ms	4572 KB	Output is correct
15	Correct	1392 ms	8392 KB	Output is correct
16	Correct	38 ms	4572 KB	Output is correct
17	Correct	1107 ms	7304 KB	Output is correct
18	Correct	530 ms	4696 KB	Output is correct
19	Correct	31 ms	4572 KB	Output is correct
20	Correct	1993 ms	10184 KB	Output is correct
21	Execution timed out	2012 ms	10444 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Correct	90 ms	4680 KB	Output is correct
20	Correct	18 ms	4572 KB	Output is correct
21	Correct	1392 ms	8392 KB	Output is correct
22	Correct	38 ms	4572 KB	Output is correct
23	Correct	1107 ms	7304 KB	Output is correct
24	Correct	530 ms	4696 KB	Output is correct
25	Correct	31 ms	4572 KB	Output is correct
26	Correct	1993 ms	10184 KB	Output is correct
27	Execution timed out	2012 ms	10444 KB	Time limit exceeded
28	Halted	0 ms	0 KB	-

Subtask #9
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	0 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	0 ms	364 KB	Output is correct
6	Correct	0 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	0 ms	364 KB	Output is correct
11	Correct	0 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	512 KB	Output is correct
14	Correct	0 ms	364 KB	Output is correct
15	Correct	1 ms	492 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	0 ms	364 KB	Output is correct
19	Runtime error	276 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Halted	0 ms	0 KB	-

Submission #318619

Compilation message