oj.uz

Submission #828472

# Submission time Handle Problem Language Result Execution time Memory
828472 2023-08-17T10:09:31 Z Yey Safety (NOI18_safety) C++14
4 / 100
 2000 ms 2684 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];
	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
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 Runtime error 2 ms 1620 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 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 2060 ms 2684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
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 Runtime error 2 ms 1620 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
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 Runtime error 2 ms 1620 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
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 Runtime error 2 ms 1620 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

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 Runtime error 2 ms 1620 KB Execution killed with signal 11
5 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 Runtime error 2 ms 1620 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -