oj.uz

Submission #559562

# Submission time Handle Problem Language Result Execution time Memory
559562 2022-05-10T07:55:11 Z zaneyu Job Scheduling (CEOI12_jobs) C++14
100 / 100
 504 ms 1272 KB 
/*input
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4 
*/
#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;
//order_of_key #of elements less than x
// find_by_order kth element
typedef unsigned long long int ll;

#define ld long double
#define pii pair<int,int>
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=3e3+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?" ":"");
    return out;
}
ll mult(ll a,ll b){
    if(a<0) a+=MOD;
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
ll dp[maxn][maxn];
int cnt[maxn];
int n,d;
bool wk(int mid){
    priority_queue<int,vector<int>,greater<int>> pq;
    REP1(i,n){
        REP(j,cnt[i]) pq.push(i);
        REP(j,mid){
            if(!sz(pq)) break;
            int z=pq.top();
            if(z+d<i){
                return false;
            }
            pq.pop();
        }
    }
    return true;
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int m;
    cin>>n>>d>>m;
    REP(i,m){
        int x;
        cin>>x;
        cnt[x]++;
    }
    int l=0,r=m;
    while(l<r){
        int mid=(l+r)/2;
        if(wk(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
    REP(i,n) cout<<"0\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1256 KB Output is correct
2 Correct 46 ms 1228 KB Output is correct
3 Correct 47 ms 1264 KB Output is correct
4 Correct 52 ms 1212 KB Output is correct
5 Correct 67 ms 1232 KB Output is correct
6 Correct 46 ms 1272 KB Output is correct
7 Correct 44 ms 1272 KB Output is correct
8 Correct 44 ms 1260 KB Output is correct
9 Correct 45 ms 560 KB Output is correct
10 Correct 63 ms 572 KB Output is correct
11 Correct 30 ms 328 KB Output is correct
12 Correct 125 ms 504 KB Output is correct
13 Correct 119 ms 344 KB Output is correct
14 Correct 233 ms 760 KB Output is correct
15 Correct 140 ms 340 KB Output is correct
16 Correct 158 ms 348 KB Output is correct
17 Correct 237 ms 352 KB Output is correct
18 Correct 504 ms 456 KB Output is correct
19 Correct 404 ms 576 KB Output is correct
20 Correct 243 ms 348 KB Output is correct