Cod sursa(job #3296086)

Utilizator fantomcristi fantom Data 11 mai 2025 12:02:59
Problema Transport Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("transport.in");
ofstream cout("transport.out");
vector <int> sirDeSaltele;
int  n, k;
bool PoateTransporta(int capacitate) {
    int transporturi = 1;
    int volumCurent = 0;
    for (int i = 0; i < sirDeSaltele.size(); i++) {
        if (volumCurent + sirDeSaltele[i] <= capacitate) {
            volumCurent += sirDeSaltele[i];
        }
        else {
            transporturi++;
            volumCurent = sirDeSaltele[i];
            if (transporturi > k) {
                return false;
            }
        }
    }
    return true;
}
int main() {
    int suma = 0, maxim = 0;
    cin >> n >> k;
    sirDeSaltele.resize(n);
    for (int i = 0; i < sirDeSaltele.size(); i++) {
        cin >> sirDeSaltele[i];
        suma += sirDeSaltele[i];
        maxim = max(maxim, sirDeSaltele[i]);
    }
    int stanga = maxim, dreapta = suma,rezultat = suma;
    while (stanga <= dreapta) {
        int mijloc = stanga + (dreapta - stanga) / 2;
        if (PoateTransporta(mijloc)) {
            rezultat = mijloc;
            dreapta = mijloc - 1;
        }
        else {
            stanga = mijloc + 1;
        }
    }
    cout << rezultat;
    return 0;
}