Submission #1309220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309220		liptonek	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	332 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

int besthub(int r, int l, int *x, long long b)
{
    vector<long long> p(r+1);

    p[0]=0;

    for(int k=0; k<r; k++)
    {
        p[k+1]=p[l]+x[k];
    }

    int fields=0;
    int i=0;

    for(int j=0; j<r; j++)
    {
        while(i<=j)
        {
            int m=(i+j)/2;
            long long median=x[m];
            
            long long sr=p[j+1]-p[m+1];
            long long sl=p[m]-p[i];
            long long cr=j-m;
            long long cl=m-i;

            long long cost=(sr-cr*median)+(cl*median-sl);

            if(cost<=b)
            {
                if(j-i+1>fields)
                {
                    fields=j-i+1;
                }

                break;
            }
            else
            {
                i++;
            }
        }
    }

    return fields;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32