답안 #57978 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57978	2018-07-16T15:04:39 Z	jorik	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	19 ms	5600 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #57978

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 30.0 / 30.0

Subtask #3 52.0 / 52.0

Subtask #1
18.0 / 18.0

Subtask #2
30.0 / 30.0

Subtask #3
52.0 / 52.0