oj.uz

Submission #54861

# Submission time Handle Problem Language Result Execution time Memory
54861 2018-07-05T08:22:09 Z FLDutchman Rice Hub (IOI11_ricehub) C++14
68 / 100
 34 ms 3324 KB 
#include "bits/stdc++.h"
#include "ricehub.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vi;

vi prefix, suffix;
vi rice;

ll MAX;

int cost(int l, int r){
    int m = (l+r)/2;
    ll c = prefix[r] - prefix[m] - rice[m] * (r-m);
    c += suffix[l] - suffix[m] - (MAX - rice[m]) * (m-l);
    return c;
}

bool possible(int l, int r, ll B){
    //cout <<l << " " << r << " " << cost(l,r) << endl;
    return cost(l, r) <= B;
}

int besthub(int R, int L, int X[], ll B)
{
    MAX = L;
    rice.resize(R);
    for(int i = 0; i < R; i++) rice[i] = X[i];
    prefix.assign(R+1, 0); suffix.assign(R+1, 0);
    for(int i = 1; i <= R; i++) prefix[i] = prefix[i-1] + rice[i-1];
    for(int i = R-1; i >= 0; i--) suffix[i] = suffix[i+1] + L - rice[i];
    ll l = 0, r = 0;
    ll best = -1;
    while(!(l == R and r == R)){
        while(possible(l, r, B)){
            best = max(best, r-l);
            if(r < R) r++;
            else break;
        }
        l++;
    }

    return best;
}
/*
int test[] = {1, 2, 10, 12, 14};
int main(){
    
    cout << besthub(5, 20, test, 6)<<endl;
}
*/

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1276 KB Output is correct
2 Correct 5 ms 1276 KB Output is correct
3 Correct 34 ms 3324 KB Output is correct
4 Incorrect 22 ms 3324 KB Output isn't correct
5 Halted 0 ms 0 KB -