oj.uz

Submission #345172

# Submission time Handle Problem Language Result Execution time Memory
345172 2021-01-07T05:51:18 Z daniel920712 Rice Hub (IOI11_ricehub) C++14
0 / 100
 1000 ms 1000 KB 
#include "ricehub.h"
#include <algorithm>
#include <vector>
using namespace std;
vector < long long > all;
vector < long long > a,b;
int besthub(int R, int L, int X[], long long B)
{
    long long now=0,i,j,ans=0,t=0,x,y=0;
    for(i=0;i<R;i++)
    {
        a.push_back(X[i]-X[0]);
        if(i) a[i]+=a[i-1];
    }
    for(i=0;i<R;i++)
    {
        b.push_back(X[R-1]-X[i]);
        if(i) b[i]+=b[i-1];
    }
    ans=max(upper_bound(a.begin(),a.end(),B)-a.begin(),upper_bound(b.begin(),b.end(),B)-b.begin());
    a.clear();
    b.clear();
    now=0;
    for(i=0;i<R;i++)
    {
        if(now+(X[i]-X[0])>B)
        {
            t=i;
            x=i;
            break;
        }
        now+=X[i]-X[0];
    }
    //printf("0 %lld %lld %lld %lld\n",x,y,t,now);
    y=0;
    ans=max(ans,t);
    for(i=1;i<R;i++)
    {

        now+=(X[i]-X[i-1])*(y+1);
        now-=(X[i]-X[i-1])*(x-1);
        y++;
        x--;

        if(x==0)
        {
            x++;
            t++;
        }
        while(1)
        {
            if(x==1||y==0) break;
            if(i-y-1>=0&&X[i+x-1]-X[i]>=X[i]-X[i-y-1])
            {
                now-=X[i+x-1]-X[i];
                now+=X[i]-X[i-y-1];
                x--;
                y++;
            }
            else if(i+x<R&&X[i+x]-X[i]<=X[i]-X[i-y])
            {
                now+=X[i+x]-X[i];
                now-=X[i]-X[i-y];
                y--;
                x++;
            }
        }
        while(now>B)
        {
            if(y==0)
            {
                now-=X[i+x-1]-X[i];
                x--;
                t--;
            }
            else if(X[i+x-1]-X[i]<=X[i]-X[i-y])
            {
                now-=X[i]-X[i-y];
                y--;
                t--;
            }
            else
            {
                now-=X[i+x-1]-X[i];
                x--;
                t--;
            }
        }

        while(now<=B)
        {
            if(i+x>=R&&i-y-1>=0)
            {
                if(now+X[i]-X[i-y-1]<=B)
                {
                    y++;
                    t++;
                    now+=X[i]-X[i-y-1];
                }
                else break;
            }

            else if(i+x<R&&i-y-1<0)
            {
                if(now+X[i+x]-X[i]<=B)
                {
                    x++;
                    t++;
                    now+=X[i+x]-X[i];
                }
                else break;
            }
            else if(i+x<R&&i-y-1>=0)
            {
                if(X[i+x]-X[i]<=X[i]-X[i-y-1])
                {
                    if(now+X[i+x]-X[i]<=B)
                    {
                        x++;
                        t++;
                        now+=X[i+x]-X[i];
                    }
                    else break;
                }
                else
                {
                    if(now+X[i]-X[i-y-1]<=B)
                    {
                        y++;
                        t++;
                        now+=X[i]-X[i-y-1];
                    }
                    else break;
                }
            }
            else break;
        }
        ans=max(ans,t);
    }
    return (int) ans;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:9:23: warning: unused variable 'j' [-Wunused-variable]
    9 |     long long now=0,i,j,ans=0,t=0,x,y=0;
      |                       ^
ricehub.cpp:41:30: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |         now-=(X[i]-X[i-1])*(x-1);
      |                            ~~^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Execution timed out 1085 ms 364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 1084 ms 364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 1000 KB Time limit exceeded
2 Halted 0 ms 0 KB -