oj.uz

Submission #768077

# Submission time Handle Problem Language Result Execution time Memory
768077 2023-06-27T12:26:46 Z lollipop Self Study (JOI22_ho_t2) C++17
0 / 100
 283 ms 10804 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 3e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
int a[ N ] , b[ N ] , n , m ; 
int check( int mid ){
	 int lf = m * n ;
	 FOR( i , n ){
	    int nd = 0 , gn = mid  ; 
	    if( a[ i ] * m <= gn ){
	    	nd += m ; 
	    	gn = gn - a[ i ] * m ; 
		}
		else{
			nd = nd + ( gn + a[ i ] - 1 ) / a[ i ] ;
			gn = 0 ; 
		}
		if( gn != 0 ){
			nd = nd + ( gn + b[ i ] - 1 ) / b[ i ] ; 
		}
		lf = lf - nd ; 
	 }
	 if( lf >= 0 ) return 1 ;
	 return -1 ; 
}
void solve(){
     cin >> n >> m ; 
     FOR( i , n ) cin >> a[ i ] ;
     FOR( i , n ){
     	cin >> b[ i ] ; 
     	a[ i ] = max( a[ i ] , b[ i ] ) ; 
	 }
     int ans = 0 , l = 0 , r = inf ; 
     while( l < r ){
     	int mid = ( l + r ) / 2 ;
     	if( check( mid ) == 1 ){
     		ans = max( ans , mid ) ;
     		l = mid + 1 ; 
		 }
		 else r = mid ; 
	 }
	 if( check( l ) == 1 ) ans = max( ans , l ) ;
	 if( check( r ) == 1 ) ans = max( ans , r ) ;
	 cout << ans << "\n" ;
}
signed main() {
   ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
   int t = 1 ;// cin >> t ;
   while( t -- ){
   	 solve() ;
   }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 432 KB Output is correct
11 Correct 150 ms 10800 KB Output is correct
12 Correct 161 ms 10804 KB Output is correct
13 Correct 134 ms 8812 KB Output is correct
14 Incorrect 283 ms 8908 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 79 ms 5560 KB Output is correct
10 Correct 53 ms 3736 KB Output is correct
11 Correct 40 ms 2944 KB Output is correct
12 Correct 30 ms 2388 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Incorrect 5 ms 340 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 432 KB Output is correct
11 Correct 150 ms 10800 KB Output is correct
12 Correct 161 ms 10804 KB Output is correct
13 Correct 134 ms 8812 KB Output is correct
14 Incorrect 283 ms 8908 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 79 ms 5560 KB Output is correct
10 Correct 53 ms 3736 KB Output is correct
11 Correct 40 ms 2944 KB Output is correct
12 Correct 30 ms 2388 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Incorrect 5 ms 340 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 4 ms 432 KB Output is correct
11 Correct 150 ms 10800 KB Output is correct
12 Correct 161 ms 10804 KB Output is correct
13 Correct 134 ms 8812 KB Output is correct
14 Incorrect 283 ms 8908 KB Output isn't correct
15 Halted 0 ms 0 KB -