oj.uz

Submission #485690

# Submission time Handle Problem Language Result Execution time Memory
485690 2021-11-09T02:13:51 Z Joo Rice Hub (IOI11_ricehub) C++17
68 / 100
 19 ms 2500 KB 
#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;

const int MXN = 1e5+10;
using ll = long long;

int a[MXN];

bool chk(int sz, int R, int B){
    int med = (sz+1)>>1;
    deque<ll> dq;
    ll rightsum = 0, leftsum = 0;
    for(int i = 1; i <= med; i++){
        leftsum += a[i];
        dq.push_back(a[i]);
    }
    for(int i = med+1; i <= R; i++){
        rightsum += a[i];
        dq.push_back(a[i]);
        if(i >= sz){
            ll tot = rightsum - (sz-med)*(dq[med-1]) + (med)*dq[med-1] - leftsum;
            if(tot <= B) return true;
            leftsum -= dq.front();
            leftsum += dq[med];
            rightsum -= dq[med];
            dq.pop_front();
        }
    }
    return false;
}

int besthub(int R, int L, int X[], ll B){
    for(int i = 0; i < R; i++){
        a[i+1] = X[i];
    }

    int l = 2, r = R, ans = 1;
    while(l <= r){
        int mid = (l+r)>>1;

        if(chk(mid, R, B)){
            ans = mid;
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return ans;
}
/*
int main(void){
    int R,L,B; cin >> R >> L >> B;
    int X[R] = {};
    for(int i = 0; i < R; i++){
        cin >> X[i];
    }
    cout << besthub(R, L, X, B) << "\n";
    return 0;
}
*/

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Incorrect 19 ms 2500 KB Output isn't correct
4 Halted 0 ms 0 KB -