제출 #643562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643562		Ferid20072020	Fountain (eJOI20_fountain)	C++17	30 / 100	70 ms	4140 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , query;
	cin >> n >> query;
	vector<int> prefix(n+1 , 0);
	vector<int> costs(n+1);
	for(int i=0 ; i<n ; i++){
		int x , cost;
		cin >> x >> cost;
		costs[i+1] = cost;
	}
	for(int i=1 ; i<=n ; i++){
		prefix[i] = prefix[i-1] + costs[i];
	}
	while(query--){
		int start , weight , best = 0;
		cin >> start >> weight;
		weight += prefix[start-1];
		int l = start , r = n;
		while(l <= r){
			int mid = l + (r - l) / 2;
			if(prefix[mid] >= weight){
				best = mid;
				r = mid - 1;
			} 
			else{
				l = mid + 1;
			}
		}
		cout << best << '\n';
	}
}

• Subtask 1: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40