Submission #331360

#	Time	Username	Problem	Language	Result	Execution time	Memory
331360		Nson	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	510 ms	30572 KiB

bulves

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
	int n;
	scanf("%d", &n);

	multiset<ll> s;

	ll m = 0, b = 0; // y = m * x + b

	auto apply_prefix_min = [&]() {
		while(!s.empty() and m > 0) {
			m--;
			b += *prev(s.end());
			s.erase(prev(s.end()));
		}
	};

	ll d = 0;
	for(int i = 0; i < n; i++) {
		int aa, bb;
		scanf("%d %d", &aa, &bb);
		aa -= bb;
		d += aa;

		apply_prefix_min();
		if(d >= 0) {
			s.insert(d);
			s.insert(d);
			b -= d;
			m += 1;
		}
		else {
			s.insert(0);
			m += 1;
			b -= d;
		}
	}

	while(!s.empty() and *prev(s.end()) > d) {
		m--;
		b += *prev(s.end());
		s.erase(prev(s.end()));
	}

	printf("%lld\n", d * m + b);

}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bulves.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d %d", &aa, &bb);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36