oj.uz

Submission #916039

# Submission time Handle Problem Language Result Execution time Memory
916039 2024-01-25T07:29:45 Z yeediot Self Study (JOI22_ho_t2) C++14
10 / 100
 103 ms 18396 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define all(X) X.begin(),X.end()
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    setio();
    int n,m;
    cin>>n>>m;
    vector<pair<__int128,__int128>>v;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        v.pb({a,0});
    }
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        v[i].S=a;
    }
    int l=0,r=(int)2e18+10;
    while(l<r){
        int mm=l+r+1>>1;
        __int128 left=0;
        bool ok=1;
        for(int i=0;i<n;i++){
            if(v[i].F>=v[i].S){
                if(v[i].F*m>=mm){
                    __int128 x=ceil((double)mm/v[i].F);
                    left+=m-x;
                }
                else{
                    __int128 cur=mm;
                    cur-=m*v[i].F;
                    __int128 x=ceil((double)cur/v[i].S);
                    left-=x;
                    if(left<0){
                        ok=0;
                        break;
                    }
                }
            }
            else{
                left+=m;
                __int128 x=ceil((double)mm/v[i].S);
                left-=x;
                if(left<0){
                    ok=0;
                    break;
                }
            }
        }
        if(ok){
            l=mm;
        }
        else{
            r=mm-1;
        }
    }
    cout<<l<<'\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:37:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mm=l+r+1>>1;
      |                ~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 103 ms 17028 KB Output is correct
12 Correct 97 ms 17352 KB Output is correct
13 Correct 81 ms 18396 KB Output is correct
14 Correct 89 ms 17088 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 37 ms 18380 KB Output is correct
17 Correct 100 ms 17244 KB Output is correct
18 Correct 89 ms 18376 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 37 ms 18380 KB Output is correct
3 Correct 100 ms 17244 KB Output is correct
4 Correct 89 ms 18376 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 103 ms 17028 KB Output is correct
12 Correct 97 ms 17352 KB Output is correct
13 Correct 81 ms 18396 KB Output is correct
14 Correct 89 ms 17088 KB Output is correct
15 Incorrect 0 ms 348 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 103 ms 17028 KB Output is correct
12 Correct 97 ms 17352 KB Output is correct
13 Correct 81 ms 18396 KB Output is correct
14 Correct 89 ms 17088 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -