oj.uz

Submission #580429

# Submission time Handle Problem Language Result Execution time Memory
580429 2022-06-21T08:40:48 Z yutabi Divide and conquer (IZhO14_divide) C++14
17 / 100
 1 ms 212 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -