oj.uz

Submission #104892

# Submission time Handle Problem Language Result Execution time Memory
104892 2019-04-09T13:28:37 Z popovicirobert Rice Hub (IOI11_ricehub) C++14
49 / 100
 291 ms 3064 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector <ll> sp;
vector <int> x;

inline pair <ll, int> check(int dst, int R, int pos) {
    int l = 0, r = 0;
    for(int step = 1 << 16; step; step >>= 1) {
        if(l + step <= R && x[pos] - dst > x[l + step]) {
            l += step;
        }
        if(r + step <= R && x[pos] + dst >= x[r + step]) {
            r += step;
        }
    }
    pair <ll, int> ans;
    ans.first = 1LL * (pos - l) * x[pos] - (sp[pos] - sp[l]) + (sp[r] - sp[pos]) - 1LL * (r - pos) * x[pos];
    ans.second = r - l;
    return ans;
}

int besthub(int R, int L, int X[], long long B) {
    x.resize(R + 1), sp.resize(R + 1);
    for(int i = 1; i <= R; i++) {
        x[i] = X[i - 1];
        sp[i] = sp[i - 1] + x[i];
    }
    ll ans = 0;
    for(int i = 1; i <= R; i++) {
        int dst = -1;
        for(int step = 1 << 30; step; step >>= 1) {
            if(check(dst + step, R, i).first < B) {
                dst += step;
            }
        }
        auto cur = check(dst, R, i);
        dst++;
        ans = max(ans, cur.second + (B - cur.first) / dst);
        //cerr << i << " " << cur.first << " " << cur.second << " " << dst << "\n";
    }
    ans = min(ans, 1LL * R);
    return (int) ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Runtime error 3 ms 512 KB Execution killed with signal 8 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 668 KB Output is correct
2 Correct 43 ms 732 KB Output is correct
3 Correct 266 ms 2048 KB Output is correct
4 Correct 278 ms 3064 KB Output is correct
5 Correct 117 ms 1476 KB Output is correct
6 Correct 111 ms 1408 KB Output is correct
7 Correct 280 ms 2688 KB Output is correct
8 Correct 278 ms 2688 KB Output is correct
9 Correct 125 ms 1408 KB Output is correct
10 Correct 113 ms 1468 KB Output is correct
11 Correct 249 ms 2936 KB Output is correct
12 Correct 291 ms 3048 KB Output is correct
13 Correct 126 ms 1608 KB Output is correct
14 Correct 114 ms 1528 KB Output is correct
15 Correct 201 ms 2304 KB Output is correct
16 Correct 209 ms 2296 KB Output is correct
17 Correct 229 ms 2688 KB Output is correct
18 Correct 253 ms 2732 KB Output is correct
19 Correct 234 ms 2816 KB Output is correct
20 Correct 273 ms 2816 KB Output is correct