Dynamics programing, find ideal route between cinemas to see the most movies https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=cinemas

alg02exam.cpp

//TASK: https://cw.felk.cvut.cz/courses/a4b33alg/task.php?task=cinemas

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

#define arr std::vector

using namespace std;
#define min(a, b) ((a)<(b)?(a):(b))

#ifdef WIN32

int getchar_unlocked() { return getchar(); }

#elif UNIX
/* Do linux stuff */
#endif

static inline void scanint(int &x) {
    // fastest stdin reading, found on https://stackoverflow.com/questions/27899413/understanding-getchar-unlocked
    register int c = getchar_unlocked();
    x = 0;
    for (; (c < 48 || c > 57); c = getchar_unlocked());
    for (; c > 47 && c < 58; c = getchar_unlocked()) {
        x = (x << 1) + (x << 3) + (c & 15);
    }
}

int movie = 0;
int maxTime = 0;

arr<arr<int> > dist;
arr<arr<bool> > cinemas;
arr<int> lastTimes;

int tiemFinder = 0;

typedef struct {
    int moviesSeen = -1;
    int distanceTraveled = -1;
} result;

arr<arr<result> > cache;
result genyk;

result computeResult(int time, int cinema) {
    result welp;
    welp.distanceTraveled = 0;
    welp.moviesSeen = 0;

    //pokud uz stejne ty filmy nestiham
    if(genyk.moviesSeen > (maxTime -time)/2)
    {
        welp.moviesSeen = 0;
        return welp;
    }

    result maybe = cache[time][cinema];
    if (maybe.moviesSeen != -1)
        return maybe;


    result final;
    final.moviesSeen = 0;
    final.distanceTraveled = 0;

    // proejd vsechny kina a spust to od casu
    for (int i = 0; i < cinemas.size(); ++i) {
        auto &cine = cinemas[i];

        result tmp;

        // najdi best cas pro kino
        for (int j = time; j < cine.size(); ++j) {
            tiemFinder++;

            if (!cine[j]) continue;// kino v tomto case nevysila
            int required = time + dist[cinema][i];
            if (time != 0 && required > j) continue; //nestiham to

            // j je cas kdy se to vysila
            int newTime = j + movie; //cas kdy dokoukam film
            tmp = (time > lastTimes[i]) ? welp : computeResult(newTime, i); // pokud v tom kinÄ› uĹľ ni nepujde tak 0

            // vyberu kino, tam dojedu a shlednu film a k tomu prictu shlednute filmy od te doby stejne tak jetou vzdalenost
            tmp.moviesSeen += 1;
            tmp.distanceTraveled += dist[cinema][i];

            // zapis si nejlepsi vysledek
            if (final.moviesSeen < tmp.moviesSeen)
                final = tmp;

            else if (final.moviesSeen == tmp.moviesSeen)
                if (final.distanceTraveled > tmp.distanceTraveled)
                    final = tmp;
            break;
        }
    }

    cache[time][cinema] = final;
    return final;
}


int main() {
    int k;
    scanint(k);
    scanint(movie);

    dist.resize(k, arr<int>(k));

    cinemas.resize(k);
    lastTimes.resize(k);
    arr<int> firstTimes(k); // prvni vysialci casy pro kina

    for (int y = 0; y < k; ++y) {
        for (int x = 0; x < k; ++x) {
            int num;
            scanint(num);
            dist[y][x] = num;
        }
    }

    for (int i = 0; i < k; ++i) {
        int x;
        scanint(x);

        for (int j = 0; j < x; ++j) {
            int time;
            scanint(time);

            if (cinemas[i].size() == 0)
                firstTimes[i] = time;

            cinemas[i].resize(static_cast<unsigned int>(time + 1));
            cinemas[i][time] = true;
            lastTimes[i] = time;

            if (time > maxTime)
                maxTime = time;
        }
    }

    cache.resize(static_cast<unsigned int>(maxTime + 10), arr<result>(cinemas.size() + 2));
    genyk.moviesSeen = 0;

    for (int i = 0; i < cinemas.size(); ++i) {
        result final = computeResult(0, i);
        if (genyk.moviesSeen < final.moviesSeen)
            genyk = final;
        else if (genyk.moviesSeen == final.moviesSeen)
            if (genyk.distanceTraveled > final.distanceTraveled)
                genyk = final;
    }

    printf("%d %d\n", genyk.moviesSeen, genyk.distanceTraveled);
    //cerr << "kolikrat jsem heldal cas: " << tiemFinder << endl;
    return 0;
}