oj.uz

Submission #536012

# Submission time Handle Problem Language Result Execution time Memory
536012 2022-03-12T06:21:50 Z zaneyu Self Study (JOI22_ho_t2) C++14
10 / 100
 242 ms 11356 KB 
/*input
5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
#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()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#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)
ll sub(ll a,ll b){
    ll x=a-b;
    while(x<0) x+=MOD;
    while(x>MOD) x-=MOD;
    return x;
}
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const ll maxn=5e5+5;
const ll maxlg=__lg(maxn)+2; 
ll a[maxn],b[maxn];
ll n,m;
bool wk(ll mid){
    ll tot=0;
    REP(i,n){
        if(a[i]==b[i]){
            tot+=m;
            tot-=(mid+b[i]-1)/b[i];
            continue;
        }
        ll free=(m-((mid+a[i]-1)/a[i]));
        if(free<0) tot-=(mid-1LL*m*a[i]+b[i]-1)/b[i];
        else tot+=free;
    }
    return tot>=0;
}
int main(){
    cin>>n>>m;
    REP(i,n) cin>>a[i];
    REP(i,n) cin>>b[i],MXTO(a[i],b[i]);
    cout<<*min_element(a,a+n);
    return 0;
    ll l=0,r=INF64;
    while(l<r){
        ll mid=(l+r+1)/2;
        if(wk(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 242 ms 4940 KB Output is correct
12 Correct 222 ms 4968 KB Output is correct
13 Correct 171 ms 4928 KB Output is correct
14 Correct 176 ms 4976 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 80 ms 6108 KB Output is correct
17 Correct 238 ms 11356 KB Output is correct
18 Correct 221 ms 10732 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 80 ms 6108 KB Output is correct
3 Correct 238 ms 11356 KB Output is correct
4 Correct 221 ms 10732 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 242 ms 4940 KB Output is correct
12 Correct 222 ms 4968 KB Output is correct
13 Correct 171 ms 4928 KB Output is correct
14 Correct 176 ms 4976 KB Output is correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 242 ms 4940 KB Output is correct
12 Correct 222 ms 4968 KB Output is correct
13 Correct 171 ms 4928 KB Output is correct
14 Correct 176 ms 4976 KB Output is correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -