oj.uz

Submission #580458

# Submission time Handle Problem Language Result Execution time Memory
580458 2022-06-21T09:19:55 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 <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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 1 ms 212 KB Output isn't correct
17 Halted 0 ms 0 KB -