Submission #485634

#	Time	Username	Problem	Language	Result	Execution time	Memory
485634		5enpa1	Safety (NOI18_safety)	C++17	71 / 100	262 ms	26716 KiB

safety

#include <bits/stdc++.h>

#define int long long 
#define vec vector 
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define sq(x) (x)*(x)
#define fast_io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef pair<int,int> PII;
int f(int k, int b, int x){
	return k*x+b;
}
int k, x, b, y, sum;
// const int M = 1000;
// const int C = 200;
signed main(){
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	fast_io;
	int n, h;
	cin >> n >> h;
	vec < int > q(n);
	vec < int > w;
	for(auto &i: q) cin >> i, sum += i;
	// vec < vec < int > > dp(n, vec < int > (M, 1e18));
	// for(int i = 0; i < M; ++i)
	// 	dp[0][i] = abs(i-q[0]);
	// for(int i = 1; i < n; ++i){
	// 	for(int j = 0; j < M; ++j){
	// 		for(int k = max(0LL, j-h); k <= min(M-1, j+h); ++k)
	// 			dp[i][j] = min(dp[i-1][k]+abs(j-q[i]), dp[i][j]);
	// 	}
	// }
	// for(int k = 0; k < n; ++k){
	// 	auto i = dp[k];
	// 	int r = i[1]-i[0];
	// 	for(int j = 2; j < M; ++j){
	// 		while(i[j]-i[j-1] != r){
	// 			cout << j-1 << " ";
	// 			r++;
	// 		}
	// 	}
	// 	cout << "\n";
	// }
	// cout << "\n";
	multiset < int > one;
	multiset < int > two;
	int left = 0;
	int right = 0;
	for(int i = 0; i < n; ++i){
		one.insert(q[i]-left);
		one.insert(q[i]-left);
		while(sz(one) > sz(two)){
			auto it = one.end();
			it--;
			int adder = *it;
			adder -= right;
			adder += left;
			two.insert(adder);
			one.erase(one.find(*it));
		}
		while(sz(one) < sz(two)){
			int adder = *two.begin();
			adder += right;
			adder -= left;
			one.insert(adder);
			two.erase(two.find(adder));
		}
		auto it = one.end();
		it--;
		while((*it)+left > (*two.begin())+right){
			two.insert(*it+left-right);
			one.erase(it);
			one.insert(*two.begin()+right-left);
			two.erase(two.begin());
		}		
		// cout << q[i] << " :: ";
		// for(auto &j: one) cout << j+left << " ";
		// for(auto &j: two) cout << j+right << " ";
		// cout << "\n";
		left -= h;
		right += h;
	}
	left += h;
	right -= h;
	vec < int > fin;
	for(auto &i: one) fin.pb(i+left);
	for(auto &i: two) fin.pb(i+right);
	// for(auto &i: fin) cout << i << " ";
	// cout << "\n";
	b = -sum;
	for(int i = 0; i < n; ++i)
		b -= i*h;
	k = n;
	int ans = 1e18;
	for(int i = sz(fin)-1; i >= 0; --i){
		x = fin[i];
		y = k*x+b;
		ans = min(ans, y);
		k--;
		b = y-k*x;
	}
	cout << ans;
	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 0 / 29