Submission #1056984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056984		slivajan	Trains (BOI24_trains)	C++17	21 / 100	2097 ms	3532 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long un;
typedef vector<un> vuc;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un M = 1e9 + 7;

#define DIRECT 0
#define CACHE 1

int main(){

    un N;
    cin >> N;

    vuc D(N);
    vuc X(N);

    REP(i, 0, N){
        cin >> D[i] >> X[i];
    }

    un bound = (un)pow((double)N, 0.6666666);

    map<pair<un, un>, un> vyskyty;

    REP(i, 0, N){
        if (D[i] == 0) continue;
        if (vyskyty.find({D[i], i % D[i]}) == vyskyty.end()){
            vyskyty[{D[i], i % D[i]}] = min(X[i], (N-i) / D[i]);
        }
        else{
            vyskyty[{D[i], i % D[i]}] += min(X[i], (N-i) / D[i]);
        }
    }

    map<pair<un, un>, un> volba;
    FEAC(kv, vyskyty){
        pair<un, un> key;
        un val;

        tie(key, val) = kv;

        if (val < bound){
            volba[key] = DIRECT;
        }
        else{
            volba[key] = DIRECT;
        }
    }

    vuc DP(N, 0);
    DP[0] = 1;

    map<un, map<un, un>> cache;

    REP(i, 0, N){
        FEAC(kv, cache){
            un key;
            tie(key, ignore) = kv;

            if (cache[key].find(i % key) != cache[key].end()){
                DP[i] = (DP[i] + cache[key][i % key]) % M;
            }
        }

        if (D[i] == 0) continue;


        if (volba[{D[i], i%D[i]}] == DIRECT){
            for (un j = i + D[i]; (j < N) and (((j-i) / D[i]) <= X[i]); j += D[i]){
                DP[j] = (DP[j] + DP[i]) % M;
            }
        }
        else{
            if (cache.find(D[i]) == cache.end()) {
                cache[D[i]] = {{i % D[i], DP[i]}};
            }
            else if (cache[D[i]].find(i % D[i]) == cache[D[i]].end()){
                cache[D[i]][i % D[i]] = DP[i];
            }
            else{
                cache[D[i]][i % D[i]] += DP[i];
                cache[D[i]][i % D[i]] %= M;
            }
        }

    }

    un res = 0;

    REP(i, 0, N){
        res = (res + DP[i]) % M;
    }

    cout << res;

}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29