Submission #828478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
828478	2023-08-17T10:16:33 Z	Yey	Safety (NOI18_safety)	C++14	35 / 100	2000 ms	2644 KB

safety

#include <bits/stdc++.h>
#define inf INT_MAX
#define longlonginf LONG_LONG_MAX
#define mod  998244353
#define MAXN 5000
#define pll pair<ll,ll>
#define ll long long
#define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]";
#define yes() cout<<"YES\n";
#define no() cout<<"NO\n";
using namespace std;

ll n,m,k,q,x;
ll h;
ll ans = 0;
string subtask;
ll sub3 = 0;

void solve(){
	cin>>n>>k;
	ll dp[2][MAXN+5];
	k = min(k,(ll)5000);
	ll a[n];
	for(int i = 0 ; i < n ; i++){
		cin>>a[i];
	}
	for(int i = 0 ; i <= MAXN ; i++){
		dp[0][i] = abs(a[0]-i);
	}
	for(int i = 1 ; i < n ; i++){
		multiset<ll> s;
		for(int j = 0 ; j < k ; j++){
			s.insert(dp[0][j]);
		}
		for(int j = 0 ; j <= MAXN ; j++){
			if( j + k <= MAXN ) s.insert(dp[0][j+k]);
			if( j - k > 0 ) s.erase(s.lower_bound(dp[0][j-k-1]));
			dp[1][j] = abs(a[i]-j) + *s.begin();
			//cout<<i<<" "<<j<<" : "<<dp[i][j]<<"\n";
		}
		for(int j = 0 ; j <= MAXN ; j++){
			dp[0][j] = dp[1][j];
		}
	}
	ans = longlonginf;
	for(int i = 0 ; i <= MAXN ; i++){
		ans = min(ans,dp[0][i]);
	}
	cout<<ans<<"\n";
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin>>T;
	for(int i = 0 ; i < T ; i++){
		//cout<<"Case #"<<i+1<<": ";
		solve();
	}
	return 0;
}

/*
	not i but x
	logical operator
	wrong example/proof
	thoroughly
	wrong variables
	thinking it wrong
	bruh just try some test case
	capitals ;-;
	wrong data structure lol
	count memory usement
	corner case
	oversized array
	orders
	statements
	size initializer
	while con
	map -> array
	wrong digits??
	swapped variables??
	check if theres any variabled
	that got declared twice
	find some pattern
	name collision
	constraints??!
	mod !!
	resets
*/

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	396 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	392 KB	Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2084 ms	2644 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	396 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	392 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	117 ms	376 KB	Output is correct
14	Correct	78 ms	444 KB	Output is correct
15	Correct	151 ms	620 KB	Output is correct
16	Correct	185 ms	396 KB	Output is correct
17	Correct	176 ms	416 KB	Output is correct
18	Correct	135 ms	404 KB	Output is correct
19	Correct	85 ms	380 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	396 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	392 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	117 ms	376 KB	Output is correct
14	Correct	78 ms	444 KB	Output is correct
15	Correct	151 ms	620 KB	Output is correct
16	Correct	185 ms	396 KB	Output is correct
17	Correct	176 ms	416 KB	Output is correct
18	Correct	135 ms	404 KB	Output is correct
19	Correct	85 ms	380 KB	Output is correct
20	Correct	161 ms	596 KB	Output is correct
21	Correct	230 ms	468 KB	Output is correct
22	Correct	66 ms	376 KB	Output is correct
23	Correct	125 ms	616 KB	Output is correct
24	Correct	185 ms	468 KB	Output is correct
25	Correct	137 ms	612 KB	Output is correct
26	Correct	196 ms	424 KB	Output is correct
27	Correct	82 ms	380 KB	Output is correct

Subtask #7
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	396 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	392 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	117 ms	376 KB	Output is correct
14	Correct	78 ms	444 KB	Output is correct
15	Correct	151 ms	620 KB	Output is correct
16	Correct	185 ms	396 KB	Output is correct
17	Correct	176 ms	416 KB	Output is correct
18	Correct	135 ms	404 KB	Output is correct
19	Correct	85 ms	380 KB	Output is correct
20	Correct	161 ms	596 KB	Output is correct
21	Correct	230 ms	468 KB	Output is correct
22	Correct	66 ms	376 KB	Output is correct
23	Correct	125 ms	616 KB	Output is correct
24	Correct	185 ms	468 KB	Output is correct
25	Correct	137 ms	612 KB	Output is correct
26	Correct	196 ms	424 KB	Output is correct
27	Correct	82 ms	380 KB	Output is correct
28	Correct	928 ms	440 KB	Output is correct
29	Correct	678 ms	436 KB	Output is correct
30	Correct	1951 ms	624 KB	Output is correct
31	Correct	1523 ms	652 KB	Output is correct
32	Correct	1556 ms	468 KB	Output is correct
33	Correct	1944 ms	540 KB	Output is correct
34	Correct	1447 ms	672 KB	Output is correct

Subtask #8
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	396 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	392 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Incorrect	2 ms	340 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #9
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	396 KB	Output is correct
3	Correct	2 ms	392 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	2 ms	392 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Incorrect	2 ms	340 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Submission #828478

Compilation message