Softeer - 코딩테스트세트

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=630

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

long long min(long long a, long long b) {
	return a > b ? b : a;
}

bool f(vector<long long> &C, vector<long long> &D, long long cand) {
	long long prev = 0;
	for (int i = 0; i < C.size(); ++i) {
		if (C[i] >= cand) {
			prev = D[i];
			continue;
		}

		long long r = cand - C[i];
		long long d = D[i] + prev;
		if (r > d) return false;
	
		//D[i] = min(D[i], d - r);
		prev = min(D[i], d - r);
	}
	return true;
}


int main() {
	int N, T;
	cin >> N >> T;
	vector<long long> C(N);
	vector<long long> D(N);

	while (T--) {
		long long sum = 0;
		for (int i = 0; i < N - 1; ++i) {
			cin >> C[i] >> D[i];
			sum += C[i] + D[i];
		}
		cin >> C[N - 1];
		D[N - 1] = 0;
		sum += C[N - 1];

		long long e = sum / N;
		long long s = 0;

		if (f(C, D, e)) {
			cout << e << "\n";
			continue;
		}

		while (s < e) {
			long long m = (s + e) / 2;
			if (s == m) break;
			if (f(C, D, m)) s = m;
			else e = m;
		}

		cout << s << "\n";
	}

	return 0;
}