oj.uz

Submission #744282

# Submission time Handle Problem Language Result Execution time Memory
744282 2023-05-18T10:21:08 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
50 / 100
 185 ms 65536 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] ;

vector<ll> ans2[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(day <= S[i].first + d){ // do job i-th
            cnt++ ;
            ans2[day].push_back(S[i].second) ;
        }
        else {
            return false ;
        }
        if(cnt == mid){
            day++;
            cnt = 0 ;
        }
    }

    if(cnt == 0) day--;

    return day <= n ;
}

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

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

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

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

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

        if(solve(mid)){
            r = mid-1 ;
            ans = mid ;
        }
        else {
            l = mid+1 ;
            for(int i=1;i<=n;i++) ans2[i].clear();
        }
    }

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

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 27092 KB Output is correct
2 Correct 28 ms 27144 KB Output is correct
3 Correct 27 ms 27092 KB Output is correct
4 Correct 28 ms 27092 KB Output is correct
5 Correct 26 ms 27088 KB Output is correct
6 Correct 26 ms 27092 KB Output is correct
7 Correct 27 ms 27032 KB Output is correct
8 Correct 27 ms 27064 KB Output is correct
9 Correct 39 ms 30008 KB Output is correct
10 Correct 39 ms 29716 KB Output is correct
11 Runtime error 39 ms 35236 KB Memory limit exceeded
12 Runtime error 67 ms 50476 KB Memory limit exceeded
13 Runtime error 91 ms 58420 KB Memory limit exceeded
14 Runtime error 114 ms 65536 KB Execution killed with signal 9
15 Runtime error 124 ms 65536 KB Execution killed with signal 9
16 Runtime error 148 ms 65536 KB Execution killed with signal 9
17 Runtime error 159 ms 65536 KB Execution killed with signal 9
18 Runtime error 174 ms 65536 KB Execution killed with signal 9
19 Runtime error 185 ms 65536 KB Execution killed with signal 9
20 Runtime error 161 ms 65536 KB Execution killed with signal 9