Submission #666442

#	Time	Username	Problem	Language	Result	Execution time	Memory
666442		mutterpaneer	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	96 ms	11696 KiB

jobs

#include "bits/stdc++.h"
#ifdef LOCAL
#include "bits/debug.h"
#else
#define dd(...) 42
#endif
#define ll long long
#define ull unsigned long long
#define nl '\n'
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a) rend(a)
#define sz(a) ((int)a.size())
#define ff first
#define ss second
#define f(i, n) for (int i = 0; i < n; ++i)
// #define PROB_NAME "sliding"

using namespace std;

// const int INF = 1e9;
// const ll INFF = 1e18;
// const int M = 1e9 + 7;

ll d, h, n, m, k, p, q, x, y, z;

bool pos(vector<ll>& cnt, ll M) {
    // day i has cnt[i] tasks
    // M tasks can be done per day
    // keep feeding tasks to the machine, count days
    ll days = 0;
    ll older_tasks = 0;
    for (ll i = 1; i <= n; ++i) {
        days += (older_tasks + cnt[i]) / M;
        older_tasks = cnt[i] % M;
    }
    return days <= n + d;
}

void solve() {
    cin >> n >> d >> m;
    vector<ll> cnt(n + 1, 0);
    vector<ll> a;
    f(i, m) {
        cin >> x;
        a.push_back(x);
    }
    f(i, m) { ++cnt[a[i]]; }

    ll L = 1, R = 1e9;
    ll ans = R;
    while (L <= R) {
        ll M = L + (R - L) / 2;
        if (pos(cnt, M)) {
            ans = min(ans, M);
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    assert(ans != 1e9);
    cout << ans << nl;
}

void TESTCASES() {
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef PROB_NAME
    freopen(PROB_NAME ".in", "r", stdin);
    freopen(PROB_NAME ".out", "w", stdout);
#endif
    TESTCASES();
}

• Subtask 1: 0 / 100