Submission #1056984

#TimeUsernameProblemLanguageResultExecution timeMemory
1056984slivajanTrains (BOI24_trains)C++17
21 / 100
2097 ms3532 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...