Submission #710753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
710753	2023-03-15T17:46:24 Z	Spade1	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	88 ms	7824 KB

jobs

#include<bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define INF 2e9
#define nd second
#define st first
#define pb push_back
using namespace std;

const int N = 1e5 + 10;
int cnt[N], idx[N];
vector<int> W[N];

void solve() {
    int n, d, m; cin >> n >> d >> m;
    for (int i = 1; i <= m; ++i) {
        int j; cin >> j;
        cnt[j]++;
        W[j].pb(i);
    }

    int l = 1, r = 1e6;
    while (l < r) {
        int mid = (l+r)/2;
        bool no = 0;
        deque<pii> dq;
        for (int i = 1; i <= n; ++i) {
            dq.push_back({cnt[i], i});
            int cur = 0;
            while (!dq.empty() && cur < mid) {
                if (i - dq.front().nd > d) {
                    no = 1;
                    break;
                }
                if (dq.front().st + cur > mid) {
                    auto [w, i] = dq.front();
                    dq.pop_front();
                    dq.push_front({w-mid+cur, i});
                    cur = mid;
                }
                else {
                    cur += dq.front().st;
                    dq.pop_front();
                }
            }
            if (no) break;
        }
        if (no) l = mid+1;
        else r = mid;
    }
    cout << l << '\n';
    deque<pii> dq;
    for (int i = 1; i <= n; ++i) {
        cout << 0 << '\n';
    }
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int t = 1;
//    cin >> t;
	while (t--) {
		solve();
	}

    return 0;
}

Compilation message

jobs.cpp: In function 'void solve()':
jobs.cpp:36:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |                     auto [w, i] = dq.front();
      |                          ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	3288 KB	Output is correct
2	Correct	8 ms	3288 KB	Output is correct
3	Correct	8 ms	3288 KB	Output is correct
4	Correct	9 ms	3348 KB	Output is correct
5	Correct	10 ms	3288 KB	Output is correct
6	Correct	9 ms	3288 KB	Output is correct
7	Correct	10 ms	3288 KB	Output is correct
8	Correct	8 ms	3288 KB	Output is correct
9	Correct	20 ms	3464 KB	Output is correct
10	Correct	21 ms	3412 KB	Output is correct
11	Correct	13 ms	3244 KB	Output is correct
12	Correct	16 ms	3680 KB	Output is correct
13	Correct	22 ms	4848 KB	Output is correct
14	Correct	40 ms	5320 KB	Output is correct
15	Correct	37 ms	5604 KB	Output is correct
16	Correct	69 ms	6676 KB	Output is correct
17	Correct	81 ms	7820 KB	Output is correct
18	Correct	59 ms	7124 KB	Output is correct
19	Correct	80 ms	7272 KB	Output is correct
20	Correct	88 ms	7824 KB	Output is correct