Submission #640875

#	Time	Username	Problem	Language	Result	Execution time	Memory
640875		andreast12	Kisik (COCI19_kisik)	C++17	90 / 90	283 ms	36432 KiB

kisik

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
const int mod=998244353, maxn=1e6+5;
int n, k;
pair<ll, ll> a[maxn];
priority_queue<ll> pq;
ll tot, ans;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k;
	for(int i=1; i<=n; i++) cin >> a[i].se >> a[i].fi;
	sort(a+1, a+n+1);
	for(int i=1; i<=k; i++) {
		pq.push(a[i].se);
		tot+=a[i].se;
	}
	ans=a[k].fi*tot;
	for(int i=k+1; i<=n; i++) {
		if(a[i].se<pq.top()) {
			tot-=pq.top()-a[i].se;
			pq.pop();
			pq.push(a[i].se);
		}
		ans=min(ans, a[i].fi*tot);
	}
	cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10