oj.uz

Submission #828481

# Submission time Handle Problem Language Result Execution time Memory
828481 2023-08-17T10:21:24 Z Yey Safety (NOI18_safety) C++14
40 / 100
 1999 ms 3680 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -