oj.uz

답안 #1024096

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024096 2024-07-15T11:55:43 Z idas 쌀 창고 (IOI11_ricehub) C++11
100 / 100
 10 ms 4624 KB 
#include "ricehub.h"

#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)

typedef long long ll;

const int N=1e5+10;
ll p[N], s[N];

ll l_cost(int l, int r, int max_len, int x[])
{
    ll ret=p[r+1]-p[l];
    ret-=1LL*(r-l+1)*(max_len-x[r]);
    return ret;
}

ll r_cost(int l, int r, int max_len, int x[])
{
    ll ret=s[l]-s[r+1];
    ret-=1LL*(r-l+1)*x[l];
    return ret;
}

bool can(int val, int r, int l, int x[], long long b)
{
    FOR(i, 0, r)
    {
        if(i+val-1>=r) break;
        int lb=i, rb=i+val-1, med=(lb+rb)/2;
        ll cost=l_cost(lb, med, l, x)+r_cost(med, rb, l, x);
        if(cost<=b) return true;
    }
    return false;
}

int besthub(int r, int l, int x[], long long b)
{
    FOR(i, 1, r+1)
    {
        p[i]=p[i-1];
        p[i]+=l-x[i-1];
    }

    for(int i=r-1; i>=0; i--){
        s[i]=s[i+1];
        s[i]+=x[i];
    }

    int lft=0, rgt=r;
    while(lft<rgt){
        int m=(lft+rgt+1)/2;
        if(can(m, r, l, x, b)) lft=m;
        else rgt=m-1;
    }

    return lft;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2476 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2476 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2480 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2472 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2476 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 0 ms 2476 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2472 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2472 KB Output is correct
20 Correct 0 ms 2476 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 1 ms 2472 KB Output is correct
23 Correct 0 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 0 ms 2396 KB Output is correct
27 Correct 0 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2480 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2400 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 1 ms 2400 KB Output is correct
18 Correct 0 ms 2404 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1 ms 2408 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2408 KB Output is correct
23 Correct 1 ms 2444 KB Output is correct
24 Correct 1 ms 2404 KB Output is correct
25 Correct 1 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2400 KB Output is correct
28 Correct 1 ms 2408 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2752 KB Output is correct
2 Correct 3 ms 2912 KB Output is correct
3 Correct 9 ms 4448 KB Output is correct
4 Correct 9 ms 4624 KB Output is correct
5 Correct 5 ms 3524 KB Output is correct
6 Correct 5 ms 3432 KB Output is correct
7 Correct 9 ms 4196 KB Output is correct
8 Correct 9 ms 4392 KB Output is correct
9 Correct 5 ms 3280 KB Output is correct
10 Correct 5 ms 3420 KB Output is correct
11 Correct 9 ms 4452 KB Output is correct
12 Correct 9 ms 4568 KB Output is correct
13 Correct 5 ms 3428 KB Output is correct
14 Correct 10 ms 3428 KB Output is correct
15 Correct 8 ms 4192 KB Output is correct
16 Correct 6 ms 4192 KB Output is correct
17 Correct 8 ms 4388 KB Output is correct
18 Correct 9 ms 4456 KB Output is correct
19 Correct 8 ms 4456 KB Output is correct
20 Correct 9 ms 4480 KB Output is correct