NKBUS - Bus

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<algorithm>
#include<climits>
#include<cstdio>
#include<vector>
using namespace std;

#define N 200000
int n, m, t[N];
vector<int> a[N];

void enter() {
	scanf("%d%d",&n,&m); int staff = 0;
	for(int i = 0; i < n; ++i) {
		scanf("%d", t+i);
		int p; scanf("%d", &p); staff += p;
		while(p--) {
			int tmp; scanf("%d", &tmp);
			a[i].push_back(tmp);
		}
		sort(a[i].begin(), a[i].end());
	}
	m = min(staff, m);
}

void solve() {
	int lo = 0, hi = INT_MAX;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		int cnt = 0;
		for(int time = mid, i = 0; i < n && cnt < m; time += t[i++]) 
			cnt += upper_bound(a[i].begin(), a[i].end(), time) - a[i].begin();
		if(cnt >= m) hi = mid; else lo = mid + 1;
	}
	for(int i = 0; i < n; lo += t[i++]);
	printf("%d\n", lo);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif
	enter();
	solve();
	return 0;
}

Download