oj.uz

Submission #916027

# Submission time Handle Problem Language Result Execution time Memory
916027 2024-01-25T07:14:15 Z yeediot Self Study (JOI22_ho_t2) C++14
0 / 100
 1000 ms 18380 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;
    }
    __int128 l=0,r=(__int128)2e18+10;
    while(l<r){
        __int128 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((long double)mm/v[i].F);
                    left+=m-x;
                }
                else{
                    __int128 cur=mm;
                    cur-=m*v[i].F;
                    __int128 x=ceil((long double)cur/v[i].S);
                    left-=x;
                }
            }
            else{
                left+=m;
                __int128 x=ceil((long double)mm/v[i].S);
                left-=x;
            }
        }
        if(left>=0){
            l=mm;
        }
        else{
            r=mm-1;
        }
    }
    cout<<(int)l<<'\n';
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:37:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         __int128 mm=l+r+1>>1;
      |                     ~~~^~
Main.cpp:39:14: warning: unused variable 'ok' [-Wunused-variable]
   39 |         bool ok=1;
      |              ^~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 17 ms 736 KB Output is correct
11 Execution timed out 1078 ms 18380 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 841 ms 9936 KB Output is correct
10 Correct 575 ms 5328 KB Output is correct
11 Correct 441 ms 5584 KB Output is correct
12 Correct 333 ms 2516 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 11 ms 736 KB Output is correct
19 Correct 19 ms 736 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 552 ms 17864 KB Output is correct
22 Execution timed out 1048 ms 17088 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 17 ms 736 KB Output is correct
11 Execution timed out 1078 ms 18380 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 841 ms 9936 KB Output is correct
10 Correct 575 ms 5328 KB Output is correct
11 Correct 441 ms 5584 KB Output is correct
12 Correct 333 ms 2516 KB Output is correct
13 Correct 5 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 11 ms 736 KB Output is correct
19 Correct 19 ms 736 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 552 ms 17864 KB Output is correct
22 Execution timed out 1048 ms 17088 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 17 ms 736 KB Output is correct
11 Execution timed out 1078 ms 18380 KB Time limit exceeded
12 Halted 0 ms 0 KB -