oj.uz

Submission #211648

# Submission time Handle Problem Language Result Execution time Memory
211648 2020-03-20T22:26:46 Z mohamedsobhi777 Rice Hub (IOI11_ricehub) C++14
100 / 100
 320 ms 3572 KB 
#include <bits/stdc++.h> 
#include "ricehub.h"

using namespace std ;

const int N = 1e5 + 7 ; 

int n ; 
vector<long long> coordinates , prefix; 
long long limit ; 


long long calc(int l , int r){
    if(l>r)return 0ll; 
    return prefix[r] - (l?prefix[l-1]: 0) ;
}

long long sum_abs(int st , int en, long long x){
    int delimeter = upper_bound(coordinates.begin() + st , coordinates.begin() + en +1 , x)  - coordinates.begin() ;
    delimeter-- ; 
    long long ret = 1ll * x * (delimeter - st + 1)  - calc(st , delimeter)+ calc(delimeter+1 , en) - 1ll* (en-delimeter) * x ; 
    return ret ; 
}

bool check(int l , int r){
    int lo = -1 , hi =1e9 ; 
    long long ret = 1e17 ; 
    while(hi - lo > 1){
        int mid = (lo+hi) /2 ; 
        long long get1 = sum_abs(l , r ,mid) ; 
        long long get2 = sum_abs(l , r , mid+1) ; 
        if(get1 >  get2){
            lo = mid ; 
        }
        else {
            hi = mid ; 
        }
    }
    ret = sum_abs(l , r , lo+1) ;
    return ret <= limit ; 
}

int besthub(int R, int L, int X[], long long B)
{
    n = R ; 
    limit = B ; 
    int ans = 1 ; 
    for(int i= 0 ; i<R ; i++){
        if(prefix.size()){
            prefix.push_back(X[i] + prefix.back() ); 
        }
        else {
            prefix.push_back(X[i]);
        }
        coordinates.push_back(X[i]) ; 
    }
    int l = 0 , r = -1 ; 
    while(r< R-1 ){
        r++ ; 
        while( !check(l , r)  )l++ ; 
        ans = max(ans , r-l + 1) ;
    }
    return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 304 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Correct 5 ms 256 KB Output is correct
19 Correct 5 ms 256 KB Output is correct
20 Correct 5 ms 256 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 6 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 6 ms 304 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 6 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 6 ms 384 KB Output is correct
19 Correct 6 ms 384 KB Output is correct
20 Correct 6 ms 384 KB Output is correct
21 Correct 18 ms 512 KB Output is correct
22 Correct 18 ms 512 KB Output is correct
23 Correct 15 ms 512 KB Output is correct
24 Correct 15 ms 512 KB Output is correct
25 Correct 16 ms 512 KB Output is correct
26 Correct 16 ms 512 KB Output is correct
27 Correct 19 ms 512 KB Output is correct
28 Correct 19 ms 512 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1128 KB Output is correct
2 Correct 54 ms 1024 KB Output is correct
3 Correct 312 ms 3572 KB Output is correct
4 Correct 309 ms 3572 KB Output is correct
5 Correct 118 ms 1912 KB Output is correct
6 Correct 116 ms 1908 KB Output is correct
7 Correct 320 ms 3312 KB Output is correct
8 Correct 311 ms 3308 KB Output is correct
9 Correct 238 ms 1904 KB Output is correct
10 Correct 232 ms 1788 KB Output is correct
11 Correct 313 ms 3572 KB Output is correct
12 Correct 311 ms 3564 KB Output is correct
13 Correct 153 ms 1788 KB Output is correct
14 Correct 156 ms 1916 KB Output is correct
15 Correct 232 ms 3180 KB Output is correct
16 Correct 227 ms 3180 KB Output is correct
17 Correct 276 ms 3432 KB Output is correct
18 Correct 280 ms 3436 KB Output is correct
19 Correct 297 ms 3436 KB Output is correct
20 Correct 307 ms 3444 KB Output is correct