Submission #869003

#TimeUsernameProblemLanguageResultExecution timeMemory
869003bobbilykingBrunhilda’s Birthday (BOI13_brunhilda)C++17
20 / 100
3 ms1880 KiB
#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include<bits/stdc++.h> #include<math.h> using namespace std; typedef int ll; typedef long double ld; typedef pair<ll, ll> pl; #define K first #define V second #define G(x) ll x; cin >> x; #define GD(x) ld x; cin >> x; #define GS(s) string s; cin >> s; #define EX(x) { cout << x << '\n'; exit(0); } #define A(a) (a).begin(), (a).end() #define F(i, l, r) for (ll i = (l); i < r; ++i) #define NN 10010 #define M 1000000007 // 998244353 ll dp[NN]; ll last_p_dp[NN]; // last multiple of P's dp value vector<ll> upd[NN]; // this prime gets a new dp value at this step int main(){ // freopen("a.in", "r", stdin); // freopen("a.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); G(n) G(q) map<ll, ll> v; // might tle; replace with map? F(i, 0, n) { G(p) upd[p].push_back(p); v[0]++; } dp[0] = 0; F(i, 1, NN) { for (auto x: upd[i]) { if (i + x < NN) upd[i+x].push_back(x); if (!--v[last_p_dp[x]]) v.erase(last_p_dp[x]); } dp[i] = (v.size() ? v.begin()->K : NN) + 1; for (auto x: upd[i]) { last_p_dp[x] = dp[i]; v[dp[i]]++; } upd[i].clear(); } while (q--){ G(x) if (dp[x] >= NN) cout << "oo\n"; else cout << dp[x] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...