Submission #839573

#	Time	Username	Problem	Language	Result	Execution time	Memory
839573		model_code	Truck Driver (IOI23_deliveries)	C++17	8 / 100	94 ms	7692 KiB

deliveries

// correct/solution-st1-star.cpp

#include "deliveries.h"

#include <set>
#include <iostream>

#define MAXN 101000

using namespace std;

long long N, TIME, sumW, ans;
long long T[MAXN];
long long W[MAXN];
set<pair<long long, int>> spikeW;

void init(int NN, std::vector<int> /*UU*/, std::vector<int> /*VV*/, std::vector<int> TT, std::vector<int> WW){
	N = NN;
	for(int i=0; i<N-1; i++){
		T[i+1] = TT[i];
	}
	for(int i=0; i<N; i++){
		W[i] = WW[i];
	}
	W[0]++;

    for(int i=1; i<N; i++){
        sumW += W[i];
        spikeW.insert({W[i],i});
        ans += W[i] * T[i];
    }
    sumW += W[0];
}

long long max_time(int S, int X){
	if(S==0) X++;

    sumW -= W[S];
    ans -= W[S] * T[S];
    spikeW.erase({W[S],S});

	W[S] = X;
    sumW += W[S];
    ans += W[S] * T[S];
    spikeW.insert({W[S],S});

	auto it = spikeW.end(); it--;
    int id = (*it).second;
    if (W[id] < (sumW+1)/2){
        return 2*ans;
    }

    return 2*(ans - W[id] * T[id] + (sumW - W[id])*T[id]);
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 21
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36