Submission #1173464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173464		LucaIlie	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	8 ms	8772 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 3000;
const int MAX_K = 3000;

int s[MAX_M];
int optim[MAX_M][MAX_K];
int ind[MAX_M];

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );
    
    int n, m, k;
    int a, b, c;
    long long t;
        
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    for ( int i = 0; i < m; i++ ) {
        cin >> s[i];
        s[i]--;
    }

    for ( int i = 0; i < m - 1; i++ ) {
        long long timePassed = (long long)b * s[i];
        int stationC = s[i];
        int nrStations = 0;
        while ( nrStations <= k - m && stationC < s[i + 1] && timePassed <= t ) {
            int reachByA = min( (long long)s[i + 1] - 1, stationC + (t - timePassed) / a );
            optim[i][nrStations] = reachByA - stationC + 1;

            timePassed += (long long)c * (reachByA + 1 - stationC);
            stationC = reachByA + 1;
            nrStations++;
       }
    }

    /*for ( int i = 0; i < m - 1; i++ ) {
        for ( int j = 0; j < k; j++ )
            printf( "%d ", optim[i][j] );
        printf( "\n" );
    }*/

    int countReachable = ((long long)b * (n - 1) <= t);
    for ( int i = 0; i < m - 1; i++ ) {
        countReachable += optim[i][0];
        ind[i] = 1;
    }
    k -= m;
    for ( int i = 0; i < k; i++ ) {
        int k = 0;
        for ( int j = 1; j < m - 1; j++ ) {
            if ( optim[j][ind[j]] > optim[k][ind[k]] )
                k = j;
        }
        countReachable += optim[k][ind[k]];
        ind[k]++;
    }

    cout << countReachable - 1 << "\n";

    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52