Submission #225305

#	Time	Username	Problem	Language	Result	Execution time	Memory
225305		Ruxandra985	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	6 ms	640 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

long long a , b , c , t;
long long m;
priority_queue <pair <long long , pair <long long,long long> > > h;
long long v[5010] , w[5010];
set <long long> express;
set <long long> :: iterator it;

long long modul (long long x){

    return max(x , -x);

}

long long check (long long p1 , long long p2 , long long mid){

    return modul ((mid - 1 - p1) * a - ( (mid - p1) * c + (p2 - 1 - mid) * a));

}

long long calcul (long long x , long long y){
    long long st , dr , mid , nr;
    long long timp;

    /// cate ar deveni accesibile daca as pune undeva intre x si y
    /// pun pe prima dintre x si y care nu e accesibila

    if (express.find(x) != express.end())
        timp = (x - 1) * b; /// e statie express
    else { /// e statie semi_express
        st = 1;
        dr = m;
        while (st <= dr){
            mid = (st + dr) / 2;
            if (w[mid] < x)
                st = mid + 1;
            else dr = mid - 1;
        }
        st--;
        nr = w[st];

        timp = (nr - 1) * b + (x - nr) * c;

    }

    /// timp = timpul pana la x
    /// cb intre x si y unde as pune statia

    st = x + 1;
    dr = y - 1;
    while (st <= dr){
        mid = (st + dr) / 2;

        if (timp + (mid - x) * a <= t)
            st = mid + 1;
        else dr = mid - 1;

    }

    /// solutia e in st!!!

    if (x + 1 > y - 1 || st == y)
        return 0; /// nu ajuta cu nmc

    /// pui o statie semi_express in st

    timp = timp + (st - x) * c; /// timp pana la st

    if (timp > t)
        return 0;

    x = st;
    dr = y - 1;
    while (st <= dr){
        mid = (st + dr) / 2;

        if (timp + (mid - x) * a <= t)
            st = mid + 1;
        else dr = mid - 1;

    }

    return max(0LL , st - x);

}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    long long n , k , i ,  st , dr , mid , p , sol = 0 , elem , x , y , nr;
    long long timp;
    fscanf (fin,"%lld%lld%lld",&n,&m,&k);
    fscanf (fin,"%lld%lld%lld%lld",&a,&b,&c,&t);
    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%lld",&v[i]);
        w[i] = v[i];
        express.insert(v[i]);
    }
    sort (v + 1 , v + m + 1);

    for (i = 1 ; i <= m ; i++){
        h.push(make_pair(calcul(v[i] , v[i+1]) , make_pair(v[i] , v[i+1])));
        /// cate se aduna daca pui long longre v[i] si v[i + 1]
    }
    elem = m;

    for (p = 1 ; p <= k - m && !h.empty() ; p++){

        nr = h.top().first;
        x = h.top().second.first;
        y = h.top().second.second;
        h.pop();

        if (!nr)
            break;

        /// daca pun long longre p1 si p2, mi se adauga nr maxim

        if (express.find(x) != express.end())
            timp = (x - 1) * b; /// e statie express
        else { /// e statie semi_express
            it = express.lower_bound(x);
            it--;

            timp = (*it - 1) * b + (x - *it) * c;

        }

        /// timp = timpul pana la x
        /// cb long longre x si y unde as pune statia

        st = x + 1;
        dr = y - 1;
        while (st <= dr){
            mid = (st + dr) / 2;

            if (timp + (mid - x) * a <= t)
                st = mid + 1;
            else dr = mid - 1;

        }

        /// solutia e in st!!!

        if (x + 1 > y - 1 || st == y)
            continue;

        v[++elem] = st;

        h.push(make_pair(calcul(x , st) , make_pair(x , st)));
        h.push(make_pair(calcul(st , y) , make_pair(st , y)));


    }

    sort (v + 1 , v + elem + 1);

    for (i = 1 ; i < elem ; i++){

        if (express.find(v[i]) != express.end())
            timp = (v[i] - 1) * b; /// e statie express
        else { /// e statie semi_express
            st = 1;
            dr = m;
            while (st <= dr){
                mid = (st + dr) / 2;
                if (w[mid] < v[i])
                    st = mid + 1;
                else dr = mid - 1;
            }
            st--;
            nr = w[st];

            timp = (nr - 1) * b + (v[i] - nr) * c;

        }

        st = v[i] + 1;
        dr = v[i + 1] - 1;
        while (st <= dr){
            mid = (st + dr) / 2;

            if (timp + (mid - v[i]) * a <= t)
                st = mid + 1;
            else dr = mid - 1;

        }

        sol = sol + (st - 1) - v[i];

        if (st - 1 == v[i + 1])
            continue;

        if (express.find(v[i + 1]) != express.end())
            sol = sol + ( (v[i + 1] - 1) * b <= t ); /// e statie express
        else { /// e statie semi_express
            st = 1;
            dr = m;
            while (st <= dr){
                mid = (st + dr) / 2;
                if (w[mid] < v[i + 1])
                    st = mid + 1;
                else dr = mid - 1;
            }
            st--;
            nr = w[st];

            sol = sol + ( (nr - 1) * b + (v[i + 1] - nr) * c  <= t);

        }


    }

    fprintf (fout,"%lld",sol);

    return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:97:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld%lld",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:98:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%lld%lld%lld%lld",&a,&b,&c,&t);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:100:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&v[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52