Submission #1008357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008357		giorgi123glm	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	2137 ms	776240 KiB

ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdint>
#include <queue>
using namespace std;

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int n = 0, l = 0;
    cin >> n >> l;

    vector <int> X (n + 1);
    for (int i = 1; i <= n; i++)
        cin >> X[i];
    
    vector <int> T (n + 1);
    for (int i = 1; i <= n; i++)
        cin >> T[i];

    vector <int> prefX (n + 2);
    prefX[1] = 0;
    for (int i = 2; i <= n + 1; i++) {
        if (i <= n)
            prefX[i] = prefX[i - 1] + (X[i] - X[i - 1]);
        else
            prefX[i] = prefX[i - 1] + ((l - X[n]) + X[1]);
    }

    // Testing some stuff
    // cout << prefX[4] - prefX[3] << '\n';
    // for (int i = 1; i <= n + 1; i++) {
    //     cout << 2 << ' ' << (i - 1 % n) + 1 << " | " << prefX[i] - prefX[2] << '\n';
    // }

    // u could just do this...
    //                    time     point  vector index
    priority_queue <pair <int, pair <int, int> >, vector <pair <int, pair <int, int> > >, greater <pair <int, pair <int, int> > > > s;
    vector <vector <bool> > v;
    vector <int> rem;
    rem.reserve (n * n);
    v.reserve (n * n);
    int free = 0;

    // template
    vector <bool> template1 (n + 1);
    for (int i = 1; i <= n; i++) {
        int mindist = min (
            prefX[i] + X[1],
            l - (prefX[i] + X[1])
        );

        if (mindist > T[i])
            continue;

        s.push ({
            mindist,
            {
                i,
                free++
            }
        });

        // cout << i << ' ' << mindist << '\n';

        template1[i] = 1;
        v.push_back (template1);
        rem.push_back (1);
        template1[i] = 0;
    }

    // deallocate template1
    vector <bool> ().swap (template1);

    int ans = 0;
    // dijksta
    while (!s.empty()) {
        int p = s.top().second.first;
        int cont = s.top().second.second;
        int time = s.top().first;
        s.pop ();

        // cout << p << ' ' << time << ' ' << rem[cont] << " | ";
        // for (bool e : v[cont])
        //     cout << e << ' ';
        // cout << '\n';

        ans = max (ans, rem[cont]);

        if (ans == n)
            break;

        for (int e = 1; e <= n; e++)
            if (e != p) {
                int mindist = min (
                    abs (prefX[e] - prefX[p]),
                    l - abs (prefX[e] - prefX[p])
                );

                if (mindist + time <= T[e] && v[cont][e] == 0) {
                    s.push ({
                        mindist + time,
                        {
                            e,
                            free++
                        }
                    });

                    v[cont][e] = 1;
                    v.push_back (v[cont]);
                    rem.push_back (rem[cont] + 1);
                    v[cont][e] = 0;
                }
            }

        // deallocate
        vector <bool> ().swap (v[cont]);
    }

    cout << ans << '\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75