oj.uz

Submission #54859

# Submission time Handle Problem Language Result Execution time Memory
54859 2018-07-05T08:21:18 Z FLDutchman Rice Hub (IOI11_ricehub) C++14
68 / 100
 25 ms 3388 KB 
#include "bits/stdc++.h"
#include "ricehub.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;

vi prefix, suffix;
vi rice;

int 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;
}

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 3 ms 432 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 524 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 580 KB Output is correct
2 Correct 3 ms 580 KB Output is correct
3 Correct 3 ms 580 KB Output is correct
4 Correct 3 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 3 ms 584 KB Output is correct
10 Correct 3 ms 584 KB Output is correct
11 Correct 3 ms 584 KB Output is correct
12 Correct 2 ms 584 KB Output is correct
13 Correct 3 ms 584 KB Output is correct
14 Correct 2 ms 584 KB Output is correct
15 Correct 3 ms 620 KB Output is correct
16 Correct 2 ms 620 KB Output is correct
17 Correct 2 ms 620 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 2 ms 620 KB Output is correct
20 Correct 2 ms 620 KB Output is correct
21 Correct 2 ms 636 KB Output is correct
22 Correct 3 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 2 ms 636 KB Output is correct
26 Correct 2 ms 636 KB Output is correct
27 Correct 2 ms 636 KB Output is correct
28 Correct 2 ms 640 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 2 ms 640 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 640 KB Output is correct
18 Correct 2 ms 640 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 3 ms 640 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 4 ms 640 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 3 ms 764 KB Output is correct
27 Correct 3 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 8 ms 1148 KB Output is correct
2 Correct 6 ms 1148 KB Output is correct
3 Correct 25 ms 3388 KB Output is correct
4 Incorrect 25 ms 3388 KB Output isn't correct
5 Halted 0 ms 0 KB -