oj.uz

Submission #143884

# Submission time Handle Problem Language Result Execution time Memory
143884 2019-08-15T12:10:00 Z miguel Job Scheduling (CEOI12_jobs) C++14
0 / 100
 90 ms 504 KB 
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░█████░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░█░█░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░▄░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
#define L nod<<1
#define R ((nod<<1)|1)
#define mp make_pair
const ll mod = 1000000007;
const ll nmax=1000003;
int n, d, m, cnt[100010];

bool check(int xd){
    multiset<pi> s;
    for(int i=1; i<=n; i++){
        int aval=xd;
        if(cnt[i]) s.insert({i, cnt[i]});
        //if(xd==2){dbg(i); for(pi j: s) cout<<j.x<<" "<<j.y<<endl;}
        if(s.size() && (*s.begin()).x<i-d) return 0;
        while(aval && s.size()){
            pi cur=*s.begin();
            if(aval>=cur.y){
                s.erase(s.begin());
                aval-=cur.y;
            }
            else{
                s.erase(s.begin());
                s.insert({cur.x, cur.y-aval});
                aval=0;
            }
        }
    }
    if(s.size()==0) return 1;
    else return 0;
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>d>>m;
    for(int i=1, x; i<=m; i++){
        cin>>x;
        cnt[x]++;
    }
    //for(int i=1; i<=n; i++) cout<<cnt[i]<<" "; cout<<endl;
    int l=0, r=m;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<endl;
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 376 KB Unexpected end of file - int32 expected
2 Incorrect 10 ms 376 KB Unexpected end of file - int32 expected
3 Incorrect 10 ms 376 KB Unexpected end of file - int32 expected
4 Incorrect 10 ms 376 KB Unexpected end of file - int32 expected
5 Incorrect 10 ms 376 KB Unexpected end of file - int32 expected
6 Incorrect 10 ms 376 KB Unexpected end of file - int32 expected
7 Incorrect 11 ms 376 KB Unexpected end of file - int32 expected
8 Incorrect 10 ms 504 KB Unexpected end of file - int32 expected
9 Incorrect 12 ms 376 KB Unexpected end of file - int32 expected
10 Incorrect 13 ms 376 KB Unexpected end of file - int32 expected
11 Incorrect 14 ms 380 KB Unexpected end of file - int32 expected
12 Incorrect 21 ms 376 KB Unexpected end of file - int32 expected
13 Incorrect 30 ms 388 KB Unexpected end of file - int32 expected
14 Incorrect 54 ms 372 KB Unexpected end of file - int32 expected
15 Incorrect 47 ms 376 KB Unexpected end of file - int32 expected
16 Incorrect 70 ms 376 KB Unexpected end of file - int32 expected
17 Incorrect 85 ms 424 KB Unexpected end of file - int32 expected
18 Incorrect 76 ms 504 KB Unexpected end of file - int32 expected
19 Incorrect 90 ms 376 KB Unexpected end of file - int32 expected
20 Incorrect 85 ms 504 KB Unexpected end of file - int32 expected