oj.uz

Submission #235002

# Submission time Handle Problem Language Result Execution time Memory
235002 2020-05-26T17:20:37 Z muhammad_hokimiyon Rice Hub (IOI11_ricehub) C++14
17 / 100
 1000 ms 2040 KB 
#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n;
int r1;
int a[N];
long long p[N];
long long s;

int f( int x )
{
    int l = 1 , r = n;
    while( l < r ){
        int m = (l + r) / 2;
        if( a[m + 1] > x )r = m;
        else l = m + 1;
    }
    int res = 1;
    long long y = 0;
    for( int i = l + 1 , j = l; i <= n; i++ ){
        y += 1ll * a[i] - x;
        l = 1 , r = j;
        long long cnt = 0;
        while( l < r ){
            int m = (l + r) / 2;
            if( 1ll * x * (j - m + 1) - (p[j] - p[m - 1]) + y > s )l = m + 1;
            else r = m;
        }
        if( 1ll * x * (j - l + 1) - (p[j] - p[l - 1]) + y <= s )res = max( i - l + 1 , res );
        if( y <= s )res = max( res , i - j );
    }
    return res;
}

int besthub(int R, int L, int X[], long long B)
{
    n = R;
    r1 = L;
    for( int i = 1; i <= n; i++ )a[i] = X[i - 1];
    for( int i = 1; i <= n; i++ ){
        p[i] = p[i - 1];
        p[i] += a[i];
    }
    s = B;
    int l = 1 , r = r1;
    while( r - l >= 1000 ){
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        if( f(m1) < f(m2) )l = m1;
        else r = m2;
    }
    int ans = f(l);
    for( int i = l + 1; i <= r; i++ ){
        ans = max( ans , f(i) );
    }
    return ans;
}

Compilation message

ricehub.cpp: In function 'int f(int)':
ricehub.cpp:27:19: warning: unused variable 'cnt' [-Wunused-variable]
         long long cnt = 0;
                   ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 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 384 KB Output is correct
9 Incorrect 4 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 14 ms 432 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 640 KB Output is correct
2 Correct 236 ms 640 KB Output is correct
3 Correct 335 ms 2040 KB Output is correct
4 Execution timed out 1047 ms 1920 KB Time limit exceeded
5 Halted 0 ms 0 KB -