Submission #470086

#	Time	Username	Problem	Language	Result	Execution time	Memory
470086		peuch	Safety (NOI18_safety)	C++17	100 / 100	280 ms	20996 KiB

safety

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

const int MAXN = 2e5 + 10;

int n;
long long h;
long long ans;

multiset<long long> s1, s2;

int main(){
	scanf("%d %lld", &n, &h);
	long long id;
	scanf("%lld", &id);
	long long s1S = 0, s2S = 0;
	s1.insert(id);
	s2.insert(id);
	for(int i = 2; i <= n; i++){
		scanf("%lld", &id);
		s1S -= h;
		s2S += h;
		
		multiset<long long> :: iterator it = s1.end();
		it--;
		long long a = *it;
		long long b = *s2.begin();
		a += s1S;
		b += s2S;
		
		if(id < a) {
			ans += a - id;
			s1.insert(id - s1S);
			s1.insert(id - s1S);
		}
		else if(id > b) {
			ans += id - b;
			s2.insert(id - s2S);
			s2.insert(id - s2S);
		}
		else{
			ans += 0;
			s1.insert(id - s1S);
			s2.insert(id - s2S);
		}
		
		
		it = s1.end();
		it--;
		a = *it;
		b = *s2.begin();
		a += s1S;
		b += s2S;
		if(s1.size() > s2.size()){
			s2.insert(a - s2S);
			s1.erase(it);
		}
		else if(s2.size() > s1.size()){ 
			s1.insert(b - s1S);
			s2.erase(s2.begin());
		}
		
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

safety.cpp: In function 'int main()':
safety.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d %lld", &n, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
safety.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%lld", &id);
      |  ~~~~~^~~~~~~~~~~~~
safety.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%lld", &id);
      |   ~~~~~^~~~~~~~~~~~~

• 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: 29 / 29