Submission #51535

#	Time	Username	Problem	Language	Result	Execution time	Memory
51535		atoiz	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	34 ms	12016 KiB

semiexpress

#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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52