Submission #108927

#	Time	Username	Problem	Language	Result	Execution time	Memory
108927		AdrienVannson	Two Dishes (JOI19_dishes)	C++17	15 / 100	245 ms	53204 KiB

dishes

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;
using ll = long long;

const ll oo = 1ll<<62;

const int NB_MAX_ETAPES = 200*1000 + 42;


struct Etape
{
    ll duree;
    ll dateMaxRecompense;
    ll recompense;

    ll sommeAvant = 0;
};


int nbEtapes[2];
Etape etapes[2][NB_MAX_ETAPES];


ll dynamique[2000+1][2000+1];

ll getGainMax (const int iEtape1, const int iEtape2)
{
    ll &res = dynamique[iEtape1][iEtape2];
    if (res != -oo) {
        return res;
    }

    if (iEtape1 == nbEtapes[0] && iEtape2 == nbEtapes[1]) {
        return res = 0;
    }

    const ll date = etapes[0][iEtape1].sommeAvant + etapes[1][iEtape2].sommeAvant;

    if (iEtape1 < nbEtapes[0]) {
        ll score = getGainMax(iEtape1+1, iEtape2);

        if (date + etapes[0][iEtape1].duree <= etapes[0][iEtape1].dateMaxRecompense) {
            score += etapes[0][iEtape1].recompense;
        }

        res = max(score, res);
    }

    if (iEtape2 < nbEtapes[1]) {
        ll score = getGainMax(iEtape1, iEtape2+1);

        if (date + etapes[1][iEtape2].duree <= etapes[1][iEtape2].dateMaxRecompense) {
            score += etapes[1][iEtape2].recompense;
        }

        res = max(score, res);
    }

    return res;
}


int main ()
{
    fill(*dynamique, *dynamique+2001*2001, -oo);

    scanf("%d %d", &nbEtapes[0], &nbEtapes[1]);

    for (int i=0; i<nbEtapes[0]; i++) {
        scanf("%lld %lld %lld", &etapes[0][i].duree, &etapes[0][i].dateMaxRecompense, &etapes[0][i].recompense);
    }
    for (int i=0; i<nbEtapes[1]; i++) {
        scanf("%lld %lld %lld", &etapes[1][i].duree, &etapes[1][i].dateMaxRecompense, &etapes[1][i].recompense);
    }

    for (int iPlat=0; iPlat<2; iPlat++) {
        etapes[iPlat][0].sommeAvant = 0;
        for (int i=1; i<=nbEtapes[iPlat]; i++) {
            etapes[iPlat][i].sommeAvant = etapes[iPlat][i-1].sommeAvant + etapes[iPlat][i-1].duree;
        }
    }

    if (nbEtapes[0] <= 2000 && nbEtapes[1] <= 2000) {
        printf("%lld\n", getGainMax(0, 0));
    }
    else {
        const ll seuilGains = etapes[0][0].dateMaxRecompense;

        int iEtape0 = 0;
        int iEtape1 = 0;

        ll gainActuel = 0;

        while (iEtape0 < nbEtapes[0] && etapes[0][iEtape0+1].sommeAvant <= seuilGains) {
            gainActuel += etapes[0][iEtape0].recompense;
            iEtape0++;
        }
        while (iEtape1 < nbEtapes[1] && etapes[1][iEtape1+1].sommeAvant <= seuilGains - etapes[0][iEtape0].sommeAvant) {
            gainActuel += etapes[1][iEtape1].recompense;
            iEtape1++;
        }

        ll gainMax = gainActuel;

        while (iEtape0) {
            iEtape0--;
            gainActuel -= etapes[0][iEtape0].recompense;

            while (iEtape1 < nbEtapes[1] && etapes[1][iEtape1+1].sommeAvant <= seuilGains - etapes[0][iEtape0].sommeAvant) {
                gainActuel += etapes[1][iEtape1].recompense;
                iEtape1++;
            }

            // Il ne faut pas pouvoir reprendre l'étape que l'on vient de supprimer
            if (etapes[0][iEtape0+1].sommeAvant > seuilGains - etapes[1][iEtape1].sommeAvant) {
                gainMax = max(gainActuel, gainMax);
            }
        }

        printf("%lld\n", gainMax);
    }
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &nbEtapes[0], &nbEtapes[1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &etapes[0][i].duree, &etapes[0][i].dateMaxRecompense, &etapes[0][i].recompense);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &etapes[1][i].duree, &etapes[1][i].dateMaxRecompense, &etapes[1][i].recompense);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9