Submission #1154039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154039		Sandarach151	Akcija (COCI21_akcija)	C++20	30 / 110	1 ms	584 KiB

Main

#include<iostream>
#include<set>
using namespace std;

#define int long long

struct info{
	int count;
	int weight;
	int empty;

	info(int a, int b, int c): count(a), weight(b), empty(c) {}
	info(){
		count=0;
		weight=0;
		empty=0;
	}
};

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	pair<int, int> arr[n];
	for(int i=0; i<n; i++){
		int w, d;
		cin >> w >> d;
		arr[i] = make_pair(d-1, w);
	}
	sort(arr, arr+n);
	multiset<int, greater<int> > used;
	info dp[n];
	dp[0] = info(1, arr[0].second, arr[0].first);
	used.insert(arr[0].second);
	for(int i=1; i<n; i++){
		if(arr[i].first != arr[i-1].first){
			int cnt = dp[i-1].count+1;
			int wght = dp[i-1].weight+arr[i].second;
			int empty = dp[i-1].empty+(arr[i].first-arr[i-1].first-1);
			dp[i] = info(cnt, wght, empty);
			used.insert(arr[i].second);
		}
		else{
			if(dp[i-1].empty>0){
				int cnt = dp[i-1].count+1;
				int wght = dp[i-1].weight+arr[i].second;
				int empty = dp[i-1].empty-1;
				dp[i] = info(cnt, wght, empty);
				used.insert(arr[i].second);
			}
			else{
				if(arr[i].second < *used.begin()){
					int wght = dp[i-1].weight - *used.begin() + arr[i].second;
					used.erase(used.begin());
					used.insert(arr[i].second);
					dp[i] = dp[i-1];
					dp[i].weight = wght;
				}
				else{
					dp[i] = dp[i-1];
				}
			}
		}
	}
	cout << dp[n-1].count << ' ' << dp[n-1].weight << '\n';
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20