Submission #124075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124075	2019-07-02T13:27:53 Z	mechfrog88	Safety (NOI18_safety)	C++14	35 / 100	1004 ms	262144 KB

safety

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;	

vector <vector<ll>> sparse(15,vector<ll>(6001));

void build(vector <ll> arr){
	for (ll z=0;z<15;z++){
		for (ll x=0;x<5555;x++){
			sparse[z][x] = LLONG_MAX;
			if (x + (1 << z) - 1 < 5555){
				if (z == 0) sparse[z][x] = arr[x];
				else sparse[z][x] = min(sparse[z-1][x],sparse[z-1][x+(1<<(z-1))]);
			} 
		}
	}
}

ll query (ll l ,ll r){
	int k = 31-__builtin_clz(r-l);
	if (l == r) k = 0;
	return min(sparse[k][l],sparse[k][r - (1 << k)+1]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,d;
	cin >> n >> d;
	vector <vector<ll>> dp(n+1,vector<ll>(5555,0));
	vector <ll> arr(n+1);
	ll maxi = 0;
	for (int z=1;z<=n;z++){
		cin >> arr[z];
		maxi = max(maxi,arr[z]);
	}
	for (int z=1;z<=n;z++){
		build(dp[z-1]);
		for (int h=0;h<=maxi;h++){
			ll temp = query(max(ll(0),h-d),min(ll(maxi),h+d));
			dp[z][h] = temp+abs(arr[z]-h);
		}
	}
	ll mini = LLONG_MAX;
	for(int z=0;z<=maxi;z++){
		mini = min(dp[n][z],mini);
	}
	cout << mini << endl;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	228 ms	262144 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	4 ms	1656 KB	Output is correct
2	Correct	4 ms	1528 KB	Output is correct
3	Correct	4 ms	1528 KB	Output is correct
4	Correct	4 ms	1528 KB	Output is correct
5	Correct	4 ms	1528 KB	Output is correct
6	Correct	5 ms	1528 KB	Output is correct
7	Correct	5 ms	1528 KB	Output is correct
8	Correct	5 ms	1784 KB	Output is correct
9	Correct	5 ms	1784 KB	Output is correct
10	Correct	5 ms	1784 KB	Output is correct
11	Correct	5 ms	1784 KB	Output is correct
12	Correct	5 ms	1784 KB	Output is correct
13	Correct	89 ms	22948 KB	Output is correct
14	Correct	87 ms	22248 KB	Output is correct
15	Correct	87 ms	22264 KB	Output is correct
16	Correct	89 ms	22904 KB	Output is correct
17	Correct	79 ms	20344 KB	Output is correct
18	Correct	66 ms	17144 KB	Output is correct
19	Correct	86 ms	21940 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1656 KB	Output is correct
2	Correct	4 ms	1528 KB	Output is correct
3	Correct	4 ms	1528 KB	Output is correct
4	Correct	4 ms	1528 KB	Output is correct
5	Correct	4 ms	1528 KB	Output is correct
6	Correct	5 ms	1528 KB	Output is correct
7	Correct	5 ms	1528 KB	Output is correct
8	Correct	5 ms	1784 KB	Output is correct
9	Correct	5 ms	1784 KB	Output is correct
10	Correct	5 ms	1784 KB	Output is correct
11	Correct	5 ms	1784 KB	Output is correct
12	Correct	5 ms	1784 KB	Output is correct
13	Correct	89 ms	22948 KB	Output is correct
14	Correct	87 ms	22248 KB	Output is correct
15	Correct	87 ms	22264 KB	Output is correct
16	Correct	89 ms	22904 KB	Output is correct
17	Correct	79 ms	20344 KB	Output is correct
18	Correct	66 ms	17144 KB	Output is correct
19	Correct	86 ms	21940 KB	Output is correct
20	Correct	94 ms	21428 KB	Output is correct
21	Correct	97 ms	23004 KB	Output is correct
22	Correct	82 ms	19320 KB	Output is correct
23	Correct	78 ms	17756 KB	Output is correct
24	Correct	93 ms	21368 KB	Output is correct
25	Correct	85 ms	18168 KB	Output is correct
26	Correct	109 ms	22948 KB	Output is correct
27	Correct	101 ms	21368 KB	Output is correct

Subtask #7
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1656 KB	Output is correct
2	Correct	4 ms	1528 KB	Output is correct
3	Correct	4 ms	1528 KB	Output is correct
4	Correct	4 ms	1528 KB	Output is correct
5	Correct	4 ms	1528 KB	Output is correct
6	Correct	5 ms	1528 KB	Output is correct
7	Correct	5 ms	1528 KB	Output is correct
8	Correct	5 ms	1784 KB	Output is correct
9	Correct	5 ms	1784 KB	Output is correct
10	Correct	5 ms	1784 KB	Output is correct
11	Correct	5 ms	1784 KB	Output is correct
12	Correct	5 ms	1784 KB	Output is correct
13	Correct	89 ms	22948 KB	Output is correct
14	Correct	87 ms	22248 KB	Output is correct
15	Correct	87 ms	22264 KB	Output is correct
16	Correct	89 ms	22904 KB	Output is correct
17	Correct	79 ms	20344 KB	Output is correct
18	Correct	66 ms	17144 KB	Output is correct
19	Correct	86 ms	21940 KB	Output is correct
20	Correct	94 ms	21428 KB	Output is correct
21	Correct	97 ms	23004 KB	Output is correct
22	Correct	82 ms	19320 KB	Output is correct
23	Correct	78 ms	17756 KB	Output is correct
24	Correct	93 ms	21368 KB	Output is correct
25	Correct	85 ms	18168 KB	Output is correct
26	Correct	109 ms	22948 KB	Output is correct
27	Correct	101 ms	21368 KB	Output is correct
28	Correct	1004 ms	219000 KB	Output is correct
29	Correct	814 ms	184824 KB	Output is correct
30	Correct	958 ms	215220 KB	Output is correct
31	Correct	740 ms	178552 KB	Output is correct
32	Correct	800 ms	180304 KB	Output is correct
33	Correct	968 ms	219000 KB	Output is correct
34	Correct	965 ms	214360 KB	Output is correct

Subtask #8
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1656 KB	Output is correct
2	Correct	4 ms	1528 KB	Output is correct
3	Correct	4 ms	1528 KB	Output is correct
4	Correct	4 ms	1528 KB	Output is correct
5	Correct	4 ms	1528 KB	Output is correct
6	Correct	5 ms	1528 KB	Output is correct
7	Correct	5 ms	1528 KB	Output is correct
8	Correct	5 ms	1784 KB	Output is correct
9	Correct	5 ms	1784 KB	Output is correct
10	Correct	5 ms	1784 KB	Output is correct
11	Correct	5 ms	1784 KB	Output is correct
12	Correct	5 ms	1784 KB	Output is correct
13	Runtime error	6 ms	2936 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-

Subtask #9
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1656 KB	Output is correct
2	Correct	4 ms	1528 KB	Output is correct
3	Correct	4 ms	1528 KB	Output is correct
4	Correct	4 ms	1528 KB	Output is correct
5	Correct	4 ms	1528 KB	Output is correct
6	Correct	5 ms	1528 KB	Output is correct
7	Correct	5 ms	1528 KB	Output is correct
8	Correct	5 ms	1784 KB	Output is correct
9	Correct	5 ms	1784 KB	Output is correct
10	Correct	5 ms	1784 KB	Output is correct
11	Correct	5 ms	1784 KB	Output is correct
12	Correct	5 ms	1784 KB	Output is correct
13	Runtime error	6 ms	2936 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Halted	0 ms	0 KB	-

Submission #124075

Compilation message