oj.uz

Submission #744268

# Submission time Handle Problem Language Result Execution time Memory
744268 2023-05-18T10:14:13 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 184 ms 14948 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long ;
using pii = pair<ll , ll> ;
using i3 = tuple<ll , ll , ll> ;

const int N = 1e6+5 ;
const int MOD = 1e9+7 ;

ll n , d , m ;
pii S[N] ;

bool solve(ll mid){
    ll day = 1 , cnt = 0 ;
    for(int i=1;i<=m;i++){
        if(day < S[i].first){
            day = S[i].first ;
            cnt = 0 ;
        }
        if(cnt == mid){
            day++;
            cnt = 0 ;
        }
        if(day > S[i].first + d){
            return false ;
        }
        cnt++;
    }

    return (day <= n) ;
}

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

    cin >> n >> d >> m ;
    for(int i=1;i<=m;i++){
        ll x ;
        cin >> x ;
        S[i] = {x , i};
    }

    sort(S+1 , S+m+1) ;

    ll l = 1 , r = 1e9 , ans = 0 ;

    while(l <= r){
        ll mid = (l+r)/2 ;

        if(solve(mid)){
            r = mid-1 ;
            ans = mid ;
        }
        else {
            l = mid+1 ;
        }
    }

    cout << ans << "\n" ;
    for(int i=1;i<=n;i++){
        cout << "0\n" ;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2188 KB Output is correct
2 Correct 12 ms 2200 KB Output is correct
3 Correct 13 ms 2208 KB Output is correct
4 Correct 12 ms 2200 KB Output is correct
5 Correct 13 ms 2132 KB Output is correct
6 Correct 12 ms 2208 KB Output is correct
7 Correct 12 ms 2132 KB Output is correct
8 Correct 12 ms 2196 KB Output is correct
9 Correct 22 ms 2248 KB Output is correct
10 Correct 21 ms 2248 KB Output is correct
11 Correct 20 ms 2268 KB Output is correct
12 Correct 42 ms 3828 KB Output is correct
13 Correct 66 ms 5316 KB Output is correct
14 Correct 88 ms 7064 KB Output is correct
15 Correct 102 ms 8744 KB Output is correct
16 Correct 152 ms 10196 KB Output is correct
17 Correct 157 ms 11716 KB Output is correct
18 Correct 179 ms 13260 KB Output is correct
19 Correct 184 ms 14948 KB Output is correct
20 Correct 162 ms 11688 KB Output is correct