Submission #580469

#	Time	Username	Problem	Language	Result	Execution time	Memory
580469		yutabi	Divide and conquer (IZhO14_divide)	C++14	100 / 100	84 ms	4372 KiB

divide

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


#define pb push_back


typedef long long ll;
typedef pair <ll,ll> ii;

ll l;
ll r;
ll m;

int n;

vector <ll> x;
vector <ll> g;
vector <ll> d;

vector <ll> real_d;
vector <ll> best;

bool flag;

ll ptr1,ptr2;
ll cost;
ll gold;
ll electric;

ll xptr2;

int main()
{
    scanf("%d",&n);

    best=vector <ll> (n+1);

    g.pb(0);
    d.pb(0);

    for(int i=0;i<n;i++)
    {
        ll a,b,c;

        scanf(" %lld %lld %lld",&a,&b,&c);

        x.pb(a);

        g.pb(b);
        g[g.size()-1]+=g[g.size()-2];

        d.pb(c);
        d[d.size()-1]+=d[d.size()-2];

        real_d.pb(c);
    }

    ptr1=n-1;
    ptr2=n;

    while(1)
    {
        if(ptr1<1)
        {
            for(int i=ptr1+1;i<=ptr2;i++)
            {
                best[i]=ptr2;
            }

            break;
        }

        cost=x[ptr2-1]-x[ptr1];
        electric=d[ptr2]-d[ptr1];

        if(ptr1==2)
        {
            //printf("\n%lld %lld\n\n",cost,electric);
        }

        if(electric>=cost)
        {
            ptr1--;
        }

        else
        {
            for(int i=ptr1+2;i<=ptr2;i++)
            {
                best[i]=ptr2;
            }

            ptr2=ptr1+1;
        }
    }

    /*for(int i=1;i<=n;i++)
    {
        printf("%lld ",best[i]);
    }

    printf("\n");*/

    l=0;
    r=100000000000000007;

    m=(l+r+1)/2;

    while(l!=r)
    {
        //if(m<100)\
            printf("%lld %lld %lld\n",l,m,r);

        flag=0;

        ptr1=0,ptr2=1;

        while(1)
        {
            xptr2=best[ptr2];

            cost=x[xptr2-1]-x[ptr1];
            gold=g[xptr2]-g[ptr1];
            electric=d[xptr2]-d[ptr1];
            
            //if(m<100)\
                printf("%lld %lld %lld %lld %lld\n",ptr1,ptr2,cost,gold,electric);

            if(gold<m)
            {
                if(ptr2>=n)
                {
                    break;
                }

                ptr2++;
            }

            else
            {
                if(electric>=cost)
                {
                    flag=1;

                    break;
                }

                ptr1++;
            }
        }

        if(flag)
        {
            l=m;
        }

        else
        {
            r=m-1;
        }

        m=(l+r+1)/2;
    }

    printf("%lld\n",m);
}

Compilation message (stderr)

divide.cpp:112:9: warning: multi-line comment [-Wcomment]
  112 |         //if(m<100)\
      |         ^
divide.cpp:127:13: warning: multi-line comment [-Wcomment]
  127 |             //if(m<100)\
      |             ^
divide.cpp: In function 'int main()':
divide.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
divide.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf(" %lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52