Submission #580429

#	Time	Username	Problem	Language	Result	Execution time	Memory
580429		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 <pair <ll,ii> > s;



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

    s=vector <pair <ll,ii> > (n);


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

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

        s[i]=make_pair(a,ii(b,c));
    }

    l=0;
    r=1000000000000000007;

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

    while(l!=r)
    {
        bool flag=0;

        ll ptr1=0,ptr2=1;
        ll cost=0;
        ll gold=s[0].second.first;
        ll electric=s[0].second.second;

        while(1)
        {
            if(gold<m)
            {
                if(ptr2<n)
                {
                    cost+=s[ptr2].first-s[ptr2-1].first;

                    gold+=s[ptr2].second.first;
                    electric+=s[ptr2].second.second;

                    ptr2++;
                }

                else
                {
                    break;
                }
            }

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

                    break;
                }

                cost+=s[ptr1].first-s[ptr1+1].first;

                gold-=s[ptr1].second.first;
                electric-=s[ptr1].second.second;

                ptr1++;
            }
        }

        if(flag)
        {
            l=m;
        }

        else
        {
            r=m-1;
        }

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

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

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf(" %d",&n);
      |     ~~~~~^~~~~~~~~~
divide.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf(" %lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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