Cod sursa(job #2865187)

Utilizator catalinrus123456789Rus Catalin Stelian catalinrus123456789 Data 8 martie 2022 16:25:12
Problema Transport Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;

const int MAXN = 16005;
int N, K, s[MAXN];

inline bool Check(const int &value) {
	int transportnou = 0, transport= 1;
	for(int i = 1 ; i <= N ; ++ i) {
		if(transport+ s[i] <= value)
			transportnou += s[i];
		else {
			if(st[i] > value)
				return false;
			transportnou = s[i];
			++ transport;
		}
	}
	return transport <= K;
}

inline int binarySearch() {
	int li = 1, ls = s[0], ans = -1;
	while(li <= ls) {
		int mid = (li + ls) / 2;
		if(Check(mid)) {
			ls = mid - 1;
			ans = mid;
		}
		else li = mid + 1;
	}
	return ans;
}

int main() {
	ifstream fin("transport.in");
	ofstream fout("transport.out");
	fin >> N >> K;
	for(int i = 1 ; i <= N ; ++ i)
		fin >> s[i], s[0] += s[i];
	fout << binarySearch() << '\n';
	return 0;
}