170722025-05-20 18:37:26algoproAutózáscpp17Hibás válasz 0/100143ms7080 KiB
// UUID: e96125d3-be38-427d-846c-4dc074ddd606
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k;
	cin>>n>>k;
	vector<pair<int, int>> kut(n+1);
	for(int i=1;i<=n;i++){
		cin>>kut[i].first>>kut[i].second;
	}
	stack<int> mini;
	vector<int> nex(n+1);
	mini.push(0);
	int tav=0;
	vector<int> pref(n+1);
	for(int i=1;i<n;i++){
		pref[i+1]=pref[i]+kut[i].first;
	}
	for(int i=n;i>0;i--){
		while(kut[mini.top()].second>=kut[i].second){
			mini.pop();
		}
		if(pref[mini.top()]-pref[i]>k)nex[i]=-1;
		else nex[i]=mini.top();
		mini.push(i);
	}
	vector<pair<int, int>> valasz;
	int mennyi=0, kolt=0;
	for(int i=1;i<=n;i++){
		if(nex[i]==-1){
			kolt+=(k-mennyi)*kut[i].second;
			valasz.push_back({i, k-mennyi});
			mennyi=k;
		}
		else{
			kolt+=(pref[nex[i]]-pref[i]-mennyi)*kut[i].second;
			if(pref[nex[i]]-pref[i]-mennyi>0){
				valasz.push_back({i, pref[nex[i]]-pref[i]-mennyi});
			}			
			mennyi+=pref[nex[i]]-pref[i]-mennyi;
		}
		mennyi-=kut[i].first;
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/100
1Hibás válasz0/01ms528 KiB
2Hibás válasz0/0140ms7080 KiB
3Hibás válasz0/51ms316 KiB
4Hibás válasz0/51ms316 KiB
5Hibás válasz0/51ms316 KiB
6Hibás válasz0/51ms316 KiB
7Hibás válasz0/51ms332 KiB
8Hibás válasz0/51ms316 KiB
9Hibás válasz0/51ms316 KiB
10Hibás válasz0/51ms316 KiB
11Hibás válasz0/528ms1652 KiB
12Hibás válasz0/545ms2480 KiB
13Hibás válasz0/541ms2272 KiB
14Hibás válasz0/582ms4260 KiB
15Futási hiba0/587ms3124 KiB
16Futási hiba0/585ms3124 KiB
17Futási hiba0/586ms3100 KiB
18Futási hiba0/581ms3020 KiB
19Futási hiba0/5129ms4660 KiB
20Futási hiba0/5135ms4648 KiB
21Futási hiba0/5137ms4916 KiB
22Futási hiba0/5143ms5060 KiB