oj.uz

Submission #435315

# Submission time Handle Problem Language Result Execution time Memory
435315 2021-06-23T07:39:43 Z alextodoran Rice Hub (IOI11_ricehub) C++17
100 / 100
 326 ms 2628 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;

typedef long long ll;

int besthub (int n, int len, int pos[], ll budget)
{
    ll sumPref[n];
    for(int i = 0; i < n; i++)
    {
        if(i >= 1)
            sumPref[i] = sumPref[i - 1];
        else
            sumPref[i] = 0;
        sumPref[i] += pos[i];
    }

    int answer = 0;
    for(int hub = 0; hub < n; hub++)
    {
        function <pair <ll, int> (int)> eval = [&] (int maxDist)
        {
            ll cost = 0;
            int cnt = 0;
            {
                int l = 0, r = hub;
                while(l < r)
                {
                    int mid = (l + r) / 2;
                    if(pos[hub] - pos[mid] <= maxDist)
                        r = mid;
                    else
                        l = mid + 1;
                }
                assert(l == r);

                ll sumSeg = sumPref[hub];
                if(l >= 1)
                    sumSeg -= sumPref[l - 1];
                int cntSeg = (hub - l + 1);

                cost += 1LL * pos[hub] * cntSeg - sumSeg;
                cnt += cntSeg;
            }
            if(hub < n - 1)
            {
                int l = hub + 1, r = n - 1;
                while(l < r)
                {
                    int mid = (l + r + 1) / 2;
                    if(pos[mid] - pos[hub] <= maxDist)
                        l = mid;
                    else
                        r = mid - 1;
                }
                assert(l == r);

                ll sumSeg = sumPref[r];
                sumSeg -= sumPref[hub];
                int cntSeg = (r - hub);

                cost += sumSeg - 1LL * pos[hub] * cntSeg;
                cnt += cntSeg;
            }
            return make_pair(cost, cnt);
        };

        int maxDist;
        {
            int l = 0, r = len;
            while(l < r)
            {
                int mid = (l + r + 1) / 2;
                pair <ll, int> e = eval(mid);
                if(e.first <= budget)
                    l = mid;
                else
                    r = mid - 1;
            }
            assert(l == r);
            maxDist = l;
        }
        maxDist++;
        pair <ll, int> e = eval(maxDist);
        int over;
        if(e.first > budget)
            over = ((e.first - budget) + maxDist - 1) / maxDist;
        else
            over = 0;
        answer = max(answer, e.second - over);
    }
    return answer;
}

int brute (int n, int len, int pos[], ll budget)
{
    int answer = 0;
    for(int hub = 0; hub < n; hub++)
    {
        for(int l = 0; l <= hub; l++)
        {
            ll cost = 0;
            int cnt = 1;
            for(int i = hub - l; i < hub; i++)
            {
                cost += pos[hub] - pos[i];
                cnt++;
            }
            if(cost > budget)
                break;
            for(int i = hub + 1; i < n; i++)
            {
                cost += pos[i] - pos[hub];
                if(cost > budget)
                    break;
                cnt++;
            }
            answer = max(answer, cnt);
        }
    }
    return answer;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 508 KB Output is correct
2 Correct 38 ms 460 KB Output is correct
3 Correct 208 ms 1456 KB Output is correct
4 Correct 326 ms 2520 KB Output is correct
5 Correct 134 ms 1208 KB Output is correct
6 Correct 134 ms 1208 KB Output is correct
7 Correct 143 ms 2124 KB Output is correct
8 Correct 211 ms 2228 KB Output is correct
9 Correct 119 ms 1220 KB Output is correct
10 Correct 114 ms 1084 KB Output is correct
11 Correct 204 ms 2524 KB Output is correct
12 Correct 314 ms 2628 KB Output is correct
13 Correct 150 ms 1252 KB Output is correct
14 Correct 151 ms 1228 KB Output is correct
15 Correct 152 ms 1848 KB Output is correct
16 Correct 229 ms 1936 KB Output is correct
17 Correct 180 ms 2280 KB Output is correct
18 Correct 276 ms 2372 KB Output is correct
19 Correct 191 ms 2380 KB Output is correct
20 Correct 294 ms 2400 KB Output is correct