oj.uz

Submission #57978

# Submission time Handle Problem Language Result Execution time Memory
57978 2018-07-16T15:04:39 Z jorik Semiexpress (JOI17_semiexpress) C++14
100 / 100
 19 ms 5600 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 4 ms 552 KB Output is correct
5 Correct 8 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 2 ms 724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 4 ms 552 KB Output is correct
5 Correct 8 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 892 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 4 ms 892 KB Output is correct
12 Correct 3 ms 892 KB Output is correct
13 Correct 3 ms 1008 KB Output is correct
14 Correct 3 ms 1020 KB Output is correct
15 Correct 2 ms 1020 KB Output is correct
16 Correct 3 ms 1020 KB Output is correct
17 Correct 3 ms 1052 KB Output is correct
18 Correct 2 ms 1052 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 4 ms 552 KB Output is correct
5 Correct 8 ms 572 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 3 ms 892 KB Output is correct
10 Correct 2 ms 892 KB Output is correct
11 Correct 4 ms 892 KB Output is correct
12 Correct 3 ms 892 KB Output is correct
13 Correct 3 ms 1008 KB Output is correct
14 Correct 3 ms 1020 KB Output is correct
15 Correct 2 ms 1020 KB Output is correct
16 Correct 3 ms 1020 KB Output is correct
17 Correct 3 ms 1052 KB Output is correct
18 Correct 2 ms 1052 KB Output is correct
19 Correct 3 ms 1136 KB Output is correct
20 Correct 3 ms 1168 KB Output is correct
21 Correct 3 ms 1200 KB Output is correct
22 Correct 4 ms 1472 KB Output is correct
23 Correct 19 ms 5548 KB Output is correct
24 Correct 4 ms 5548 KB Output is correct
25 Correct 3 ms 5548 KB Output is correct
26 Correct 4 ms 5548 KB Output is correct
27 Correct 4 ms 5548 KB Output is correct
28 Correct 3 ms 5548 KB Output is correct
29 Correct 15 ms 5600 KB Output is correct
30 Correct 10 ms 5600 KB Output is correct