oj.uz

Submission #481434

# Submission time Handle Problem Language Result Execution time Memory
481434 2021-10-20T19:55:23 Z Mihai_Eduard Rice Hub (IOI11_ricehub) C++14
68 / 100
 16 ms 2488 KB 
bool verify(long long sum[], int r, int l, int x[], long long b, int nr)
{
    int st, dr, mij;
    long long total;
    for(int i=0;i<r-nr+1;i++)
    {
        st=i+1;
        dr=i+nr;
        mij=(st+dr)/2;
        total=0;
        total=total+x[mij]*(mij-st+1);
        total=total-(sum[mij]-sum[st-1]);
        total=total+(sum[dr]-sum[mij]);
        total=total-x[mij]*(dr-mij);

        if(total<=b)
            return true;
    }
    return false;
}

int besthub(int r, int l, int x[], long long b)
{
    long long sum[100005]={};
    sum[0]=0;
    for(int i=1;i<=r;i++)
        sum[i]=sum[i-1]+x[i-1];
    int st=1, dr=r+1, mij;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(verify(sum,r,l,x,b,mij))
            st=mij;
        else
            dr=mij;
    }
    return st;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 1 ms 972 KB Output is correct
12 Correct 1 ms 972 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 1 ms 972 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 1 ms 972 KB Output is correct
24 Correct 1 ms 972 KB Output is correct
25 Correct 1 ms 972 KB Output is correct
26 Correct 1 ms 972 KB Output is correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 972 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 1 ms 972 KB Output is correct
12 Correct 1 ms 972 KB Output is correct
13 Correct 1 ms 972 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 1 ms 972 KB Output is correct
16 Correct 1 ms 972 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 1 ms 972 KB Output is correct
19 Correct 1 ms 972 KB Output is correct
20 Correct 1 ms 1024 KB Output is correct
21 Correct 1 ms 972 KB Output is correct
22 Correct 1 ms 972 KB Output is correct
23 Correct 1 ms 972 KB Output is correct
24 Correct 2 ms 972 KB Output is correct
25 Correct 1 ms 972 KB Output is correct
26 Correct 1 ms 972 KB Output is correct
27 Correct 1 ms 972 KB Output is correct
28 Correct 1 ms 972 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1100 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 16 ms 1432 KB Output is correct
4 Correct 13 ms 1356 KB Output is correct
5 Correct 7 ms 1228 KB Output is correct
6 Correct 7 ms 1580 KB Output is correct
7 Correct 12 ms 2124 KB Output is correct
8 Correct 13 ms 2220 KB Output is correct
9 Correct 8 ms 1484 KB Output is correct
10 Correct 7 ms 1484 KB Output is correct
11 Correct 13 ms 2488 KB Output is correct
12 Correct 13 ms 2460 KB Output is correct
13 Incorrect 7 ms 1564 KB Output isn't correct
14 Halted 0 ms 0 KB -