제출 #666941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666941		mutterpaneer	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	64 ms	9404 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>& tasks, ll M) {
    multiset<pair<ll, ll>> a;
    dd(tasks);
    for (ll i = 1; i < sz(tasks); ++i) {
        dd(i, a);
        if (!a.empty()) {
            ll pending = 0;
            auto L = *a.begin();
            if (L.ff + d < i) return false;
            pending = L.ss;
            if (pending <= M) {
                a.erase(a.begin());
                x = M - pending;
                ll extra = max(tasks[i] - x, 0LL);
                if (extra > 0) {
                    a.insert({i, extra});
                }
            } else {
                pending -= M;
                a.erase(a.begin());
                a.insert({L.ff, pending});
                if (tasks[i] > 0) a.insert({i, tasks[i]});
            }
        } else {
            ll extra = max(tasks[i] - M, 0LL);
            if (extra > 0) {
                a.insert({i, extra});
            }
        }
    }
    dd(a);
    if (a.empty()) return true;
    auto L = *a.begin();
    return L.ff + d <= n;
}

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 = m;
    ll ans = R;
    while (L <= R) {
        ll M = L + (R - L) / 2;
        bool res = pos(cnt, M);
        dd(L, M, R, res);
        if (res) {
            ans = min(ans, M);
            R = M - 1;
        } else {
            L = M + 1;
        }
    }
    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();
}

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'bool pos(std::vector<long long int>&, long long int)':
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:28:5: note: in expansion of macro 'dd'
   28 |     dd(tasks);
      |     ^~
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:30:9: note: in expansion of macro 'dd'
   30 |         dd(i, a);
      |         ^~
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:56:5: note: in expansion of macro 'dd'
   56 |     dd(a);
      |     ^~
jobs.cpp: In function 'void solve()':
jobs.cpp:5:17: warning: statement has no effect [-Wunused-value]
    5 | #define dd(...) 42
      |                 ^~
jobs.cpp:77:9: note: in expansion of macro 'dd'
   77 |         dd(L, M, R, res);
      |         ^~

• Subtask 1: 0 / 100