제출 #615650

#제출 시각아이디문제언어결과실행 시간메모리
615650Clan328던전 (IOI21_dungeons)C++17
0 / 100
7097 ms7544 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; int n; vector<pair<ll, ll>> G, W; vl dp; ll getDP(int i) { if (dp[i] != -1) return dp[i]; if (i == n) { dp[i] = 0; return 0; } dp[i] = W[i].first+getDP(G[i].first); return dp[i]; } void init(int nx, vi s, vi p, vi w, vi l) { n = nx; G = vector<pll>(n); W = vector<pll>(n); for (int i = 0; i < n; i++) { G[i] = {w[i], l[i]}; W[i] = {s[i], p[i]}; } dp = vl(n+1, -1); for (int i = 0; i <= n; i++) { dp[i] = getDP(i); } } ll simulate(int x, int z) { if (z >= W[0].first) return z + dp[x]; ll currStrength = z, currCnt = 0; vi cnt(n); vl strength(n); int idx = -1; for (int i = x; i != n; ) { currCnt++; if (cnt[i] != 0) { idx = i; break; } cnt[i] = currCnt; strength[i] = currStrength; if (currStrength >= W[i].first) { currStrength += W[i].first; i = G[i].first; } else { currStrength += W[i].second; i = G[i].second; } } if (idx == -1) return currStrength; if (currStrength >= W[0].first) { return currStrength + dp[idx]; } ll cycleStrength = currStrength-strength[idx]; ll remStrength = W[0].first-currStrength; currStrength += (remStrength/cycleStrength)*cycleStrength; int idx2 = -1; for (int i = idx; i != n; ) { if (currStrength >= W[0].first) { idx2 = i; break; } if (currStrength >= W[i].first) { currStrength += W[i].first; i = G[i].first; } else { currStrength += W[i].second; i = G[i].second; } } if (idx2 == -1) return currStrength; return currStrength + dp[idx2]; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...