Submission #580458

#	Time	Username	Problem	Language	Result	Execution time	Memory
580458		yutabi	Divide and conquer (IZhO14_divide)	C++14	17 / 100	1 ms	212 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;

bool flag;

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

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

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

    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)
        {
            cost=x[ptr2-1]-x[ptr1];
            gold=g[ptr2]-g[ptr1];
            electric=d[ptr2]-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:57:9: warning: multi-line comment [-Wcomment]
   57 |         //if(m<100)\
      |         ^
divide.cpp:70:13: warning: multi-line comment [-Wcomment]
   70 |             //if(m<100)\
      |             ^
divide.cpp: In function 'int main()':
divide.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
divide.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         scanf(" %lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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