Submission #1199483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199483		hyl_backup	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	1 ms	584 KiB

semiexpress

//Semiexpress
#include <iostream>
#include <queue>
#include <map>

#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )

long long n, m, k, a, b, c, t, sum, add, num_station;
long long eff_left_b, new_eff_left, local_adv, semi_adv;
long long pos, new_add;

long long arr[200007];
std::map<long long, long long> effort;
std::map<long long, long long> next_station;

std::priority_queue<std::pair<long long, int>> que;
std::pair<long long, int> pa;

int main(){
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(0);

    std::cin >> n >> m >> k;
    std::cin >> a >> b >> c;
    std::cin >> t;

    sum = 0;

    for(int i = 0; i<m; ++i){
        std::cin >> arr[i];
        --arr[i];
    }

    sum=-1;

    for(int i = 0; (i<m-1)&&(arr[i]*b<=t); ++i){

        eff_left_b=t-arr[i]*b;
        local_adv=eff_left_b/a;
        add=MIN(arr[i]+local_adv, arr[i+1]-1);
        add+=-arr[i]+1;
        sum+=add;

        if(arr[i]+local_adv+1<arr[i+1]){
            new_eff_left=(eff_left_b-(local_adv+1)*c);
            if(new_eff_left<0){
                continue;
            }
            semi_adv=new_eff_left/a+1;

            add=MIN(arr[i]+local_adv+semi_adv ,arr[i+1]-1);
            add-=arr[i]+local_adv;

            que.push({add, arr[i]+local_adv+1});

            effort[arr[i]+local_adv+1]=new_eff_left;
            next_station[arr[i]+local_adv+1]=arr[i+1];
            ///how many more could i get, arr[i]+cat
            //std::cout <<arr[i]+local_adv+1 <<"pos ";
            //std::cout <<add <<"add ";
            //std::cout <<new_eff_left <<"new effort left\n";
        }
    }

    if(arr[m-1]*b<=t){
        ++sum;
    }

    num_station=m;

    while(!que.empty()){
        if(num_station==k){
            break;
        }
        ++num_station;
        pa=que.top();
        que.pop();

        add=pa.first;
        pos=pa.second;

        sum+=add;

        ///Calculate the future
        if(pos+add>=next_station[pos]){
            continue;
        }

        new_eff_left=effort[pos]-add*c;
        if(new_eff_left<0){
            //std::cout << pos << "pos while eff<0\n";
            continue;
        }

        semi_adv=new_eff_left/a+1;


        new_add=MIN(pos+add-1+semi_adv ,next_station[pos]-1);
        new_add-=pos+add-1;

        que.push({new_add, pos+add});

        effort[pos+add]=new_eff_left;
        next_station[pos+add]=next_station[pos];
        ///how many more could i get, arr[i]+cat
        //std::cout <<pos+add <<"pos ";
        //std::cout <<new_add <<"add ";
        //std::cout <<new_eff_left <<"new effort left\n";

    }


    if(sum<0){
        sum=0;
    }
    std::cout << sum;

    return 0;
}

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