Submission #927027

#TimeUsernameProblemLanguageResultExecution timeMemory
927027Gromp15Soccer (JOI17_soccer)C++17
35 / 100
3052 ms19028 KiB
#include <bits/stdc++.h> #define ll long long #define ar array #define db double #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rint(l, r) uniform_int_distribution<int>(l, r)(rng) template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } void test_case() { int h, w, a, b, c; cin >> h >> w >> a >> b >> c; int n; cin >> n; vector<ar<int, 2>> p(n); for (auto &x : p) cin >> x[0] >> x[1]; // dp[x][y] = min cost to have a player at (x, y) possessing the ball // after a player gets the ball and moves and kicks the ball, they will not move again const int dx[]{0, 1, -1, 0}, dy[]{1, 0, 0, -1}; auto in = [&](int x, int y) { return x >= 0 && y >= 0 && x <= h && y <= w; }; vector<vector<int>> dp2(h+1, vector<int>(w+1, 1e9)); { queue<ar<int, 2>> q; for (int i = 0; i < n; i++) { auto [x, y] = p[i]; dp2[x][y] = 0; q.push({x, y}); } while (q.size()) { auto [x, y] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; if (!in(nx, ny)) continue; if (ckmin(dp2[nx][ny], dp2[x][y] + 1)) { q.push({nx, ny}); } } } } const ll INF = 1e18; vector<vector<ll>> dp(h+1, vector<ll>(w+1, INF)); dp[p[0][0]][p[0][1]] = 0; set<ar<ll, 3>> q; q.insert({0, p[0][0], p[0][1]}); while (q.size()) { auto [weight, x, y] = *q.begin(); q.erase(q.begin()); // spread by walking for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; ll new_cost = dp[x][y] + c; if (!in(nx, ny) || dp[nx][ny] <= new_cost) continue; if (dp[nx][ny] != INF) q.erase({dp[nx][ny], nx, ny}); dp[nx][ny] = new_cost; q.insert({new_cost, nx, ny}); } // spread by kicking and having someone pick it up for (int d = 0; d < 4; d++) { for (int use = 1; use <= max(h, w); use++) { int nx = x + dx[d] * use, ny = y + dy[d] * use; if (!in(nx, ny)) break; ll new_cost = dp[x][y] + (ll)dp2[nx][ny] * c + (ll)use * a + b; if (dp[nx][ny] <= new_cost) continue; if (dp[nx][ny] != INF) q.erase({dp[nx][ny], nx, ny}); dp[nx][ny] = new_cost; q.insert({new_cost, nx, ny}); } } } cout << dp[p[n-1][0]][p[n-1][1]] << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while (t--) test_case(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...