oj.uz

답안 #949543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949543 2024-03-19T10:29:52 Z GrindMachine Job Scheduling (CEOI12_jobs) C++17
100 / 100
 107 ms 3960 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    int n,d,m; cin >> n >> d >> m;
    vector<int> a(m+5);
    rep1(i,m) cin >> a[i];

    sort(a.begin()+1,a.begin()+m+1);

    auto ok = [&](int mid){
        int ptr = 1;
        rep1(i,n){
            int iter = mid;
            while(ptr <= m and a[ptr] <= i and iter--){
                if(a[ptr]+d < i) return false;
                ptr++;
            }
        }

        return ptr > m;
    };

    int l = 1, r = m;
    int ans = -1;

    while(l <= r){
        int mid = (l+r) >> 1;
        if(ok(mid)){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }

    cout << ans << endl;
    rep1(i,n){
        cout << 0 << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 8 ms 860 KB Output is correct
3 Correct 8 ms 856 KB Output is correct
4 Correct 7 ms 864 KB Output is correct
5 Correct 8 ms 860 KB Output is correct
6 Correct 7 ms 860 KB Output is correct
7 Correct 7 ms 860 KB Output is correct
8 Correct 8 ms 856 KB Output is correct
9 Correct 15 ms 860 KB Output is correct
10 Correct 15 ms 1016 KB Output is correct
11 Correct 11 ms 860 KB Output is correct
12 Correct 22 ms 1116 KB Output is correct
13 Correct 33 ms 1624 KB Output is correct
14 Correct 49 ms 1884 KB Output is correct
15 Correct 54 ms 2396 KB Output is correct
16 Correct 74 ms 2808 KB Output is correct
17 Correct 86 ms 3200 KB Output is correct
18 Correct 103 ms 3576 KB Output is correct
19 Correct 107 ms 3960 KB Output is correct
20 Correct 86 ms 3188 KB Output is correct