oj.uz

Submission #435294

# Submission time Handle Problem Language Result Execution time Memory
435294 2021-06-23T07:12:48 Z alextodoran Rice Hub (IOI11_ricehub) C++17
17 / 100
 186 ms 2480 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;
                }

                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;
                }

                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 = ((e.first - budget) + maxDist - 1) / maxDist;
        answer = max(answer, e.second - over);
    }
    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 204 KB Output is correct

Subtask #2
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 Incorrect 1 ms 304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 576 KB Output is correct
2 Correct 43 ms 644 KB Output is correct
3 Incorrect 186 ms 2480 KB Output isn't correct
4 Halted 0 ms 0 KB -