oj.uz

Submission #16996

# Submission time Handle Problem Language Result Execution time Memory
16996 2015-11-03T17:46:42 Z erdemkiraz Rice Hub (IOI11_ricehub) C++
0 / 100
 20 ms 17348 KB 
#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1e6 + 5;

int n;
int a[N];
ll m;
ll L[N];

int ptr, ans = 1;

ll getL(int i, int j) {
    return (ll) (j - i + 1) * a[j] - (L[j] - L[i - 1]);
}

ll getR(int i, int j) {
    return L[j] - L[i - 1] - (ll) (j - i + 1) * a[i];
}

bool check(int i, int j) {
    ll need = getL(i, j);
    if(need > m)
        return 0;
    while(ptr + 1 <= n and a[ptr + 1] - a[j] <= a[j] - a[i])
        ptr++;
    if(getL(i, j) + getR(j, ptr) <= m) {
        ans = max(ans, ptr - i + 1);
        return 1;
    }
    return 0;
}

void solve() {
    for(int i = 1; i <= n; i++)
        L[i] = L[i - 1] + a[i];
    :: ptr = 1;
    int ptr = 1;
    for(int i = 1; i <= n; i++) {
        while(ptr + 1 <= n and check(i, ptr + 1))
            ptr++;
    }
}

int besthub(int R, int L, int X[], long long B) {
    n = R;
    m = B;
    for(int i = 0; i < n; i++) {
        a[i + 1] = X[i];
        X[i] = L - X[i] + 1;
    }
    for(int i = 1; i <= n; i++) {
        a[i] = X[n - i];
    }
    solve();
    return ans;
}

Subtask #1
0.0 / 17.0

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

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17348 KB Output is correct
2 Correct 0 ms 17348 KB Output is correct
3 Correct 0 ms 17348 KB Output is correct
4 Correct 0 ms 17348 KB Output is correct
5 Correct 0 ms 17348 KB Output is correct
6 Correct 0 ms 17348 KB Output is correct
7 Correct 0 ms 17348 KB Output is correct
8 Correct 0 ms 17348 KB Output is correct
9 Correct 0 ms 17348 KB Output is correct
10 Correct 0 ms 17348 KB Output is correct
11 Correct 0 ms 17348 KB Output is correct
12 Correct 0 ms 17348 KB Output is correct
13 Correct 0 ms 17348 KB Output is correct
14 Correct 0 ms 17348 KB Output is correct
15 Correct 0 ms 17348 KB Output is correct
16 Correct 0 ms 17348 KB Output is correct
17 Correct 0 ms 17348 KB Output is correct
18 Correct 0 ms 17348 KB Output is correct
19 Correct 0 ms 17348 KB Output is correct
20 Correct 0 ms 17348 KB Output is correct
21 Incorrect 0 ms 17348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

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

Subtask #4
0.0 / 32.0

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