Submission #57978

#	Time	Username	Problem	Language	Result	Execution time	Memory
57978		jorik	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	19 ms	5600 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

//int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
//int dirs[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

int main()
{
    //freopen("inp.in", "r", stdin);
    //freopen("outp.out", "w", stdout);
    //ios::sync_with_stdio(false);
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    long long local_cost, express_cost, semi_express_cost;
    scanf("%lld %lld %lld", &local_cost, &express_cost, &semi_express_cost);
    long long available_time;
    scanf("%lld", &available_time);
    vector<int> express_stops;
    for(int i=0; i<M; i++)
    {
        int st;
        scanf("%d", &st);
        express_stops.push_back(st);
    }
    sort(express_stops.begin(), express_stops.end());
    int ans=0;
    if((N-1)*express_cost<=available_time) ans++;
    int to_place=K-M;
    priority_queue<long long> pq;
    for(int i=0; i+1<express_stops.size(); i++)
    {
        int express_stop=express_stops[i];
        long long time_to_get_here=(express_stop-1)*express_cost;
        if(time_to_get_here>available_time) continue;
        long long over=(available_time-time_to_get_here);
        long long aantal_te_bereiken=(over/local_cost)+1;
        long long furthest_reachable=express_stop+aantal_te_bereiken-1;
        furthest_reachable=min(furthest_reachable,1LL*express_stops[i+1]-1);
        ans+=(furthest_reachable-express_stop+1);
        int tot=-3;
        while(true)
        {
            if(tot>to_place) break;
            if(furthest_reachable+1==express_stops[i+1]) break;
            over=available_time-((express_stop-1)*express_cost+(furthest_reachable+1-express_stop)*semi_express_cost);
            if(over<0) break;
            tot++;
            aantal_te_bereiken=(over/local_cost)+1;
            long long semi_stop=furthest_reachable+1;
            furthest_reachable=furthest_reachable+1+aantal_te_bereiken-1;
            if(furthest_reachable>=express_stops[i+1])
            {
                furthest_reachable=express_stops[i+1]-1;
                pq.push(furthest_reachable-semi_stop+1);
                break;
            }
            else
            {
                pq.push(furthest_reachable-semi_stop+1);
            }
        }
    }
    while(!pq.empty() && to_place>0)
    {
        to_place--;
        long long x = pq.top();
        pq.pop();
        ans += x;
    }
    ans--;
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i+1<express_stops.size(); i++)
                  ~~~^~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &local_cost, &express_cost, &semi_express_cost);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &available_time);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &st);
         ~~~~~^~~~~~~~~~~

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