oj.uz

Submission #77792

# Submission time Handle Problem Language Result Execution time Memory
77792 2018-09-30T12:29:43 Z muradeyn Rice Hub (IOI11_ricehub) C++14
17 / 100
 24 ms 1736 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
#define SIZE 100001

using namespace std;

int besthub(int r, int l, int x[], long long b)
{
    long long pre[r + 1];
    pre[0] = 0;
    for (int i = 1;i<=r;i++)pre[i] = pre[i - 1] + 1LL*x[i - 1];
    int ret = 0;
    long long le = 0,ri = r - 1;
    while (le <= ri) {
        bool f = false;
        int mid = (le + ri) / 2;
        for (int i = 0;i<r;i++) {
            if (i + mid > r)continue;
            long long cost = 0;
            long long st = i , en = i + mid - 1 , med = (st + en) / 2;
            cost += (med - st) * x[med];
            cost -= pre[med] - pre[st];
            cost += pre[en + 1] - pre[med + 1];
            cost -= (en - med) * x[med];
            if (cost <= b) {
                ret = max(ret,mid);
                f = true;
            }
        }
        if (f) le = mid + 1;
        else ri = mid - 1;
    }
    return ret;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct

Subtask #2
0 / 25.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

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