oj.uz

Submission #60712

# Submission time Handle Problem Language Result Execution time Memory
60712 2018-07-24T15:03:02 Z theknife2001 Rice Hub (IOI11_ricehub) C++17
100 / 100
 38 ms 14800 KB 
#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
const int N=1e5+55;
long long sum[N];
long long pos[N];
int n;



bool ok(int x, long long b)
{
    long long best,cur;
    best=1e18+55;
    for(int i=0;i<=n-x;i++)
    {
        cur=pos[x/2+i]*(x/2)-sum[i+x/2-1];
        if(i)
            cur+=sum[i-1];
        cur+=sum[i+x-1]-sum[i+(x-1)/2]-pos[x/2+i]*(x/2);
//        cur=0;
//        for(int j=i;j<i+x;j++)
//        {
//            cur+=abs(pos[j]-pos[i+x/2]);
//        }
        best=min(best,cur);
    }
    if(best>b)
        return 0;
    return 1;
}

int besthub(int N, int L, int X[], long long B)
{
    n=N;
    for(int i=0;i<n;i++)
    {
        pos[i]=X[i];
        sum[i]=X[i];
        if(i)
            sum[i]+=sum[i-1];
    }
    int l=2;
    int r=n+1;
    int mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(ok(mid,B))
            l=mid+1;
        else
            r=mid;
    }
    return l-1;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 3 ms 272 KB Output is correct
3 Correct 3 ms 476 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 3 ms 488 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 956 KB Output is correct
2 Correct 6 ms 956 KB Output is correct
3 Correct 32 ms 2492 KB Output is correct
4 Correct 30 ms 3516 KB Output is correct
5 Correct 21 ms 3516 KB Output is correct
6 Correct 20 ms 3516 KB Output is correct
7 Correct 25 ms 5100 KB Output is correct
8 Correct 25 ms 6000 KB Output is correct
9 Correct 23 ms 6000 KB Output is correct
10 Correct 19 ms 6000 KB Output is correct
11 Correct 30 ms 7508 KB Output is correct
12 Correct 38 ms 8588 KB Output is correct
13 Correct 13 ms 8588 KB Output is correct
14 Correct 22 ms 8588 KB Output is correct
15 Correct 21 ms 9748 KB Output is correct
16 Correct 20 ms 10544 KB Output is correct
17 Correct 28 ms 11780 KB Output is correct
18 Correct 23 ms 12756 KB Output is correct
19 Correct 28 ms 13828 KB Output is correct
20 Correct 38 ms 14800 KB Output is correct