oj.uz

Submission #51535

# Submission time Handle Problem Language Result Execution time Memory
51535 2018-06-18T08:06:41 Z atoiz Semiexpress (JOI17_semiexpress) C++14
100 / 100
 34 ms 12016 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<ll> v1;
typedef vector<v1> v2;

ll localSpeed, semiSpeed, expSpeed;
ll maxTime, expNo, localNo, semiNo, addNo;
v1 expStations;
v2 bestSelection;

//#define cin in
//ifstream in("input.txt");

int main()
{
    ios_base::sync_with_stdio(0); cin.tie();
    cin >> localNo >> expNo >> semiNo;
    addNo = semiNo - expNo;
	cin >> localSpeed >> expSpeed >> semiSpeed;
	cin >> maxTime;

	expStations.assign(expNo, 0);
	for (int i = 0; i < expNo; ++i) cin >> expStations[i];

    bestSelection = v2(expNo, v1(addNo + 1, 0));


    for (int idx = 0; idx < expNo; ++idx) {
		ll startStation = expStations[idx];
		ll endStation = (idx == expNo - 1) ? localNo + 1 : expStations[idx + 1];

		ll leftArrival = expSpeed * (startStation - 1);

		ll length = endStation - startStation;

		ll leftCnt = 1.0 * (maxTime - leftArrival) / localSpeed + 1; // index 1
		if (maxTime < leftArrival) leftCnt = 0;

        leftCnt = min(leftCnt, length);

        bestSelection[idx][0] = leftCnt;
//		cerr << "bestSelection " << idx << ' ' << 0 << ": " << bestSelection[idx][0] << endl;
//		cerr << startStation << ' ' << endStation << ' ' << leftArrival << endl;
//		cerr << length << ' ' << leftCnt << endl;


		ll newLeft, leftSemi;

        for (int add = 1; add <= addNo; ++add) {
			ll leftTime = maxTime - leftArrival;
//			if (idx == 0) cerr << add << ": " << leftTime << endl;
			if (leftTime - semiSpeed * leftCnt >= 0) {
				leftSemi = leftCnt + 1;
				leftTime -= (leftSemi - 1) * semiSpeed;
				newLeft = leftSemi + leftTime / localSpeed;
				newLeft = min(length, newLeft);
			} else newLeft = 0;

			leftCnt = newLeft;

            bestSelection[idx][add] = leftCnt;
//            cerr << "bestSelection " << idx << ' ' << add << ": " << bestSelection[idx][add] << endl;
//            cerr << leftSemi << endl;
//            cerr << newLeft << endl;
//            cerr << leftCnt << endl;
        }

        // note: [)
    }

    v1 idxs(expNo, 1);
	priority_queue< pair<int, int> > pq;
	ll cnt = -1;
	for (int i = 0; i < expNo; ++i) {
		cnt += bestSelection[i][0];
	}
//	cerr << cnt << endl;
	for (int i = 0; i < expNo; ++i) {
        if (addNo >= 1) pq.push({bestSelection[i][1] - bestSelection[i][0], i});
	}

	for (int a = 0; a < addNo; ++a) {
        pair<int, int> p = pq.top();
        pq.pop();

        int i = p.second, j = idxs[i];
        cnt += p.first;
        idxs[i]++;
        if (j > addNo) continue;
        pq.push({bestSelection[i][j+1] - bestSelection[i][j], i});
//        cerr << bestSelection[i][j+1] - bestSelection[i][j] << ' ' << i << ' ' << j << endl;
	}
	cout << cnt << endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 668 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Correct 3 ms 684 KB Output is correct
14 Correct 3 ms 684 KB Output is correct
15 Correct 2 ms 732 KB Output is correct
16 Correct 2 ms 772 KB Output is correct
17 Correct 3 ms 800 KB Output is correct
18 Correct 3 ms 800 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 3 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 684 KB Output is correct
13 Correct 3 ms 684 KB Output is correct
14 Correct 3 ms 684 KB Output is correct
15 Correct 2 ms 732 KB Output is correct
16 Correct 2 ms 772 KB Output is correct
17 Correct 3 ms 800 KB Output is correct
18 Correct 3 ms 800 KB Output is correct
19 Correct 10 ms 5856 KB Output is correct
20 Correct 20 ms 12016 KB Output is correct
21 Correct 3 ms 12016 KB Output is correct
22 Correct 6 ms 12016 KB Output is correct
23 Correct 34 ms 12016 KB Output is correct
24 Correct 3 ms 12016 KB Output is correct
25 Correct 3 ms 12016 KB Output is correct
26 Correct 3 ms 12016 KB Output is correct
27 Correct 3 ms 12016 KB Output is correct
28 Correct 3 ms 12016 KB Output is correct
29 Correct 11 ms 12016 KB Output is correct
30 Correct 8 ms 12016 KB Output is correct