Submission #200265

#	Time	Username	Problem	Language	Result	Execution time	Memory
200265		wilwxk	Safety (NOI18_safety)	C++14	66 / 100	2076 ms	1744 KiB

safety

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct point {
	ll x, y;
};

const int MAXN = 2e5+5;
vector<point> s;
int v[MAXN];
int n, x;

void expand() {
	ll mn = 1e18;
	for(auto pp : s) mn = min(mn, pp.y);

	int l = -1, r = -1;
	for(int i = 0; i < s.size(); i++) {
		if(s[i].y == mn) {
			if(l == -1) l = i;
			r = i;
		}
	}

	vector<point> aux;
	for(int i = 0; i < s.size(); i++) {
		if(i <= l) aux.push_back({s[i].x-x, s[i].y});
		if(i >= r) aux.push_back({s[i].x+x, s[i].y});
	}
	swap(aux, s);
}

void update(ll cur) {
	if(s.empty()) {
		s.push_back({v[cur], 0});
		return;
	}
	expand();
	// printf("bleh %lld\n", cur);
	// for(auto pp : s) printf("(%lld %lld) ", pp.x, pp.y); cout << endl;
	vector<point> aux;
	for(int i = 0; i < s.size(); i++) {
		if(s[i].x >= v[cur]) {
			if(i == 0) aux.push_back({ v[cur], s[i].y+(s[i].x-v[cur])*(cur-1) });
			else aux.push_back({ v[cur], ((v[cur]-s[i-1].x)*(s[i].y-s[i-1].y))/(s[i].x-s[i-1].x)+s[i-1].y });
			break;
		}
		aux.push_back(s[i]);
	}
	for(auto pp : s) if(pp.x >= v[cur]) aux.push_back(pp);
	if(aux.size() == s.size()) aux.push_back({ v[cur], (v[cur]-s.back().x)*(cur-1)+s.back().y });

	for(int i = 0; i < aux.size(); i++) aux[i].y += abs(aux[i].x-v[cur]);

	swap(aux, s);
	// for(auto pp : s) printf("(%lld %lld) ", pp.x, pp.y); cout << endl;
}

int main() {
	scanf("%d %d", &n, &x);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
		update(i);
	}

	ll ans = 1e18;
	for(auto cur : s) ans = min(ans, cur.y);
	printf("%lld\n", ans);
}

Compilation message (stderr)

safety.cpp: In function 'void expand()':
safety.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
safety.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
safety.cpp: In function 'void update(ll)':
safety.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < s.size(); i++) {
                 ~~^~~~~~~~~~
safety.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < aux.size(); i++) aux[i].y += abs(aux[i].x-v[cur]);
                 ~~^~~~~~~~~~~~
safety.cpp: In function 'int main()':
safety.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &x);
  ~~~~~^~~~~~~~~~~~~~~~~
safety.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~

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