Cod sursa(job #719170)

Utilizator mottyMatei-Dan Epure motty Data 21 martie 2012 15:31:43
Problema Zebughil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("zebughil.in");
ofstream out("zebughil.out");

const int N = 18;

int v[N];

inline bool cmp(int a, int b) {
    return (a > b);
}

int main() {
    int t = 3;
    while (t--) {
        int n, maxSize;
        in >> n >> maxSize;

        for (int i = 1; i <= n; ++i)
            in >> v[i];
        sort(v+1, v+n+1, cmp);

        vector <int> trucks;

        for (int i = 1; i <= n; ++i) {
            bool done = false;

            for (int j = 0; j < trucks.size(); ++j)
                if (trucks[j] + v[i] <= maxSize) {
                    trucks[j] += v[i];
                    done = true;
                    break;
                }

            if (done == false)
                trucks.push_back(v[i]);
        }

        out << trucks.size() << "\n";
    }

    return 0;
}