oj.uz

Submission #435314

# Submission time Handle Problem Language Result Execution time Memory
435314 2021-06-23T07:39:06 Z alextodoran Rice Hub (IOI11_ricehub) C++17
0 / 100
 41 ms 588 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)
{
    cout << n << " " << len << " " << budget << "\n";
    for(int i = 0; i < n; i++)
        cout << pos[i] << " ";
    cout << "\n";
    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;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -