Submission #520012

#TimeUsernameProblemLanguageResultExecution timeMemory
520012GiantpizzaheadSoccer (JOI17_soccer)C++17
35 / 100
997 ms24848 KiB
/* Solution: Runtime: */ #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); i++) #define sz(x) ((int) x.size()) #define all(x) x.begin(), x.end() #define debug if (true) cerr using ll = long long; const int MAXD = 505; const ll INF = 1e18; int H, W, N; int si, sj, ei, ej; ll A, B, C; ll costP[MAXD][MAXD]; int ci[] = {1, 0, -1, 0}, cj[] = {0, 1, 0, -1}; inline bool inBounds(int i, int j) { return i >= 0 && i < H && j >= 0 && j < W; } // 0-3 = Being kicked, 4 = Player has the ball ll bestC[MAXD][MAXD][5]; struct Loc { int i, j, k; ll c; bool operator<(const Loc& o) const { return c > o.c; } }; priority_queue<Loc> pq; void tryTrans(int i, int j, int k, ll c) { if (!inBounds(i, j) || bestC[i][j][k] <= c) return; bestC[i][j][k] = c; pq.push({i, j, k, c}); } void bfs() { bestC[si][sj][4] = 0; pq.push({si, sj, 4, 0}); while (!pq.empty()) { Loc l = pq.top(); pq.pop(); int i = l.i, j = l.j, k = l.k; ll c = l.c; if (k == 4) { // Player has the ball rep(d, 0, 4) { tryTrans(i + ci[d], j + cj[d], 4, c + C); // Move with the ball tryTrans(i, j, d, c + B); // Kick the ball in a direction } } else { // Ball is being kicked // Continue moving the ball tryTrans(i + ci[k], j + cj[k], k, c + A); // Stop moving and have a player pick up the ball tryTrans(i, j, 4, c + costP[i][j]); } } } void solve() { cin >> H >> W; H++, W++; cin >> A >> B >> C; cin >> N; rep(i, 0, H) rep(j, 0, W) { costP[i][j] = INF; rep(k, 0, 5) bestC[i][j][k] = INF; } rep(k, 0, N) { int i, j; cin >> i >> j; if (k == 0) si = i, sj = j; else if (k == N-1) ei = i, ej = j; rep(d, 0, 4) { int ni = i, nj = j; ll currC = 0; while (inBounds(ni, nj)) { costP[ni][nj] = min(currC, costP[ni][nj]); ni += ci[d], nj += cj[d], currC += C; } } } bfs(); ll ans = INF; rep(i, 0, H) rep(j, 0, W) rep(k, 0, 5) { ll cost = bestC[i][j][k] + C * (abs(ei-i) + abs(ej-j)); ans = min(cost, ans); } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...