답안 #828481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
828481	2023-08-17T10:21:24 Z	Yey	Safety (NOI18_safety)	C++14	40 / 100	1999 ms	3680 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];
	}
	if( k == 0 ){
		sort(a,a+n);
		x = 0;
		ans = longlonginf;
		for(int i = 0 ; i < n ; i++){
			x += a[i];
		}
		ll pref = 0;
		for(int i = 0 ; i < n ; i++){
			pref += a[i];
			x -= a[i];
			ans = min((i+1)*a[i] - pref + x - (n-(i+1))*a[i],ans);
		}
		cout<<ans<<"\n";
		return;
	}
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 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	340 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	340 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	1416 KB	Output is correct
2	Correct	27 ms	3608 KB	Output is correct
3	Correct	29 ms	3680 KB	Output is correct

Subtask #5
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 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	340 KB	Output is correct
8	Correct	0 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	113 ms	372 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	165 ms	608 KB	Output is correct
16	Correct	175 ms	460 KB	Output is correct
17	Correct	165 ms	340 KB	Output is correct
18	Correct	156 ms	396 KB	Output is correct
19	Correct	88 ms	376 KB	Output is correct

Subtask #6
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 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	340 KB	Output is correct
8	Correct	0 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	113 ms	372 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	165 ms	608 KB	Output is correct
16	Correct	175 ms	460 KB	Output is correct
17	Correct	165 ms	340 KB	Output is correct
18	Correct	156 ms	396 KB	Output is correct
19	Correct	88 ms	376 KB	Output is correct
20	Correct	161 ms	612 KB	Output is correct
21	Correct	207 ms	468 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	127 ms	596 KB	Output is correct
24	Correct	183 ms	468 KB	Output is correct
25	Correct	134 ms	608 KB	Output is correct
26	Correct	188 ms	416 KB	Output is correct
27	Correct	101 ms	340 KB	Output is correct

Subtask #7
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 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	340 KB	Output is correct
8	Correct	0 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	113 ms	372 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	165 ms	608 KB	Output is correct
16	Correct	175 ms	460 KB	Output is correct
17	Correct	165 ms	340 KB	Output is correct
18	Correct	156 ms	396 KB	Output is correct
19	Correct	88 ms	376 KB	Output is correct
20	Correct	161 ms	612 KB	Output is correct
21	Correct	207 ms	468 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	127 ms	596 KB	Output is correct
24	Correct	183 ms	468 KB	Output is correct
25	Correct	134 ms	608 KB	Output is correct
26	Correct	188 ms	416 KB	Output is correct
27	Correct	101 ms	340 KB	Output is correct
28	Correct	963 ms	412 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1999 ms	600 KB	Output is correct
31	Correct	1533 ms	632 KB	Output is correct
32	Correct	1493 ms	340 KB	Output is correct
33	Correct	1916 ms	520 KB	Output is correct
34	Correct	1404 ms	648 KB	Output is correct

Subtask #8
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 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	340 KB	Output is correct
8	Correct	0 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	3 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	340 KB	Output is correct
8	Correct	0 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	-

답안 #828481

Compilation message