oj.uz

Submission #703387

# Submission time Handle Problem Language Result Execution time Memory
703387 2023-02-27T08:24:32 Z Aestivate Self Study (JOI22_ho_t2) C++17
62 / 100
 279 ms 14252 KB 
#include<bits/stdc++.h>
#include<random>
using namespace std;

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

#define float double
#define ss(n) fixed<<setprecision(n) 
#define ll long long
#define int ll
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define rep(i,a) for(int i=1;i<=a;i++)
#define rep0(i,a) for(int i=0;i<a;i++)
#define F first
#define S second
#define uni(a) a.resize(distance(a.begin(),unique(a.begin(),a.end())));
#define unisort(a) sort(a.begin(),a.end()); uni(a);

ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}

const ld pi=3.14159265358979323846264338327950288419716939931;
const int lar=3e18;
const int mol1=1e9+7;
const int mol2=998244353;
const int MX=3e5;


void solve()
{
    int n,m;
    cin>>n>>m;
    int a[n+1],b[n+1];
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    if(n*m<=300000){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>>now;
    rep(i,n) now.push({0,i});int vis[n+1]={0};rep(j,n) vis[j]=0;
    rep(i,m*n){
        pair<int,int>kk=now.top();
        if(vis[kk.S]<m){
            kk.F+=max(a[kk.S],b[kk.S]);
            vis[kk.S]++;
        }
        else {
            kk.F+=b[kk.S];
        }
        now.pop();
        now.push(kk);
    
    }
    cout<<now.top().F<<"\n";}


    else{
        int l=m,r=1e18;
        int ans=0;
        while(l<r){
            int tt=0;
            int mid=l+r+1>>1;
            rep(i,n){
                if(a[i]>b[i]){
                    if(a[i]*m>=mid){
                        tt+=(mid/a[i])+(mid%a[i]?1:0);
                    }
                    else{
                        tt+=m;
                        int g1=mid-a[i]*m;
                        tt+=(g1/b[i])+(g1%b[i]?1:0);
                    }
                }
                else{
                    tt+=(mid/b[i])+(mid%b[i]?1:0);
                }
            }
            if(tt<=n*m) {
                ans=max(ans,mid);
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        cout<<ans<<"\n";
    }
}

signed main()
{
    IO
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:64:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |             int mid=l+r+1>>1;
      |                     ~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 96 ms 13296 KB Output is correct
12 Correct 104 ms 13360 KB Output is correct
13 Correct 101 ms 13316 KB Output is correct
14 Correct 88 ms 13316 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 69 ms 14160 KB Output is correct
17 Correct 125 ms 14128 KB Output is correct
18 Correct 100 ms 14252 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 69 ms 14160 KB Output is correct
3 Correct 125 ms 14128 KB Output is correct
4 Correct 100 ms 14252 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 65 ms 6820 KB Output is correct
14 Correct 52 ms 4288 KB Output is correct
15 Correct 39 ms 3664 KB Output is correct
16 Correct 50 ms 2768 KB Output is correct
17 Correct 17 ms 360 KB Output is correct
18 Correct 9 ms 316 KB Output is correct
19 Correct 8 ms 212 KB Output is correct
20 Correct 8 ms 320 KB Output is correct
21 Correct 7 ms 316 KB Output is correct
22 Correct 26 ms 596 KB Output is correct
23 Correct 24 ms 724 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 96 ms 13296 KB Output is correct
12 Correct 104 ms 13360 KB Output is correct
13 Correct 101 ms 13316 KB Output is correct
14 Correct 88 ms 13316 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 65 ms 6820 KB Output is correct
24 Correct 52 ms 4288 KB Output is correct
25 Correct 39 ms 3664 KB Output is correct
26 Correct 50 ms 2768 KB Output is correct
27 Correct 17 ms 360 KB Output is correct
28 Correct 9 ms 316 KB Output is correct
29 Correct 8 ms 212 KB Output is correct
30 Correct 8 ms 320 KB Output is correct
31 Correct 7 ms 316 KB Output is correct
32 Correct 26 ms 596 KB Output is correct
33 Correct 24 ms 724 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 69 ms 14160 KB Output is correct
36 Correct 125 ms 14128 KB Output is correct
37 Correct 100 ms 14252 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 320 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 27 ms 724 KB Output is correct
46 Correct 5 ms 972 KB Output is correct
47 Correct 5 ms 348 KB Output is correct
48 Correct 23 ms 3264 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 18 ms 212 KB Output is correct
51 Correct 28 ms 608 KB Output is correct
52 Correct 7 ms 212 KB Output is correct
53 Correct 12 ms 320 KB Output is correct
54 Correct 16 ms 212 KB Output is correct
55 Correct 79 ms 7612 KB Output is correct
56 Correct 53 ms 5188 KB Output is correct
57 Correct 55 ms 5192 KB Output is correct

Subtask #4
0 / 29.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 1 ms 212 KB Output is correct
9 Correct 65 ms 6820 KB Output is correct
10 Correct 52 ms 4288 KB Output is correct
11 Correct 39 ms 3664 KB Output is correct
12 Correct 50 ms 2768 KB Output is correct
13 Correct 17 ms 360 KB Output is correct
14 Correct 9 ms 316 KB Output is correct
15 Correct 8 ms 212 KB Output is correct
16 Correct 8 ms 320 KB Output is correct
17 Correct 7 ms 316 KB Output is correct
18 Correct 26 ms 596 KB Output is correct
19 Correct 24 ms 724 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 69 ms 14160 KB Output is correct
22 Correct 125 ms 14128 KB Output is correct
23 Correct 100 ms 14252 KB Output is correct
24 Correct 33 ms 1796 KB Output is correct
25 Correct 91 ms 3296 KB Output is correct
26 Correct 21 ms 1364 KB Output is correct
27 Correct 161 ms 6024 KB Output is correct
28 Correct 158 ms 5824 KB Output is correct
29 Correct 166 ms 5968 KB Output is correct
30 Correct 176 ms 5916 KB Output is correct
31 Correct 217 ms 5964 KB Output is correct
32 Incorrect 279 ms 5964 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 96 ms 13296 KB Output is correct
12 Correct 104 ms 13360 KB Output is correct
13 Correct 101 ms 13316 KB Output is correct
14 Correct 88 ms 13316 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 65 ms 6820 KB Output is correct
24 Correct 52 ms 4288 KB Output is correct
25 Correct 39 ms 3664 KB Output is correct
26 Correct 50 ms 2768 KB Output is correct
27 Correct 17 ms 360 KB Output is correct
28 Correct 9 ms 316 KB Output is correct
29 Correct 8 ms 212 KB Output is correct
30 Correct 8 ms 320 KB Output is correct
31 Correct 7 ms 316 KB Output is correct
32 Correct 26 ms 596 KB Output is correct
33 Correct 24 ms 724 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 320 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 27 ms 724 KB Output is correct
42 Correct 5 ms 972 KB Output is correct
43 Correct 5 ms 348 KB Output is correct
44 Correct 23 ms 3264 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 18 ms 212 KB Output is correct
47 Correct 28 ms 608 KB Output is correct
48 Correct 7 ms 212 KB Output is correct
49 Correct 12 ms 320 KB Output is correct
50 Correct 16 ms 212 KB Output is correct
51 Correct 79 ms 7612 KB Output is correct
52 Correct 53 ms 5188 KB Output is correct
53 Correct 55 ms 5192 KB Output is correct
54 Correct 33 ms 1796 KB Output is correct
55 Correct 91 ms 3296 KB Output is correct
56 Correct 21 ms 1364 KB Output is correct
57 Correct 161 ms 6024 KB Output is correct
58 Correct 158 ms 5824 KB Output is correct
59 Correct 166 ms 5968 KB Output is correct
60 Correct 176 ms 5916 KB Output is correct
61 Correct 217 ms 5964 KB Output is correct
62 Incorrect 279 ms 5964 KB Output isn't correct
63 Halted 0 ms 0 KB -