Submission #635923

#	Time	Username	Problem	Language	Result	Execution time	Memory
635923		Karliver	Soccer (JOI17_soccer)	C++17	100 / 100	392 ms	20084 KiB

soccer

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;
const int N = 502;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}



void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
ll d[N][N][5], com[N][N];
int n, h, w;
ll A, B, C;
PR<int> c[200001];
const long long inf = 1e18 + 2;
V<PR<int>> dir{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void solve() {	
	
	cin >> h >> w >> A >> B >> C >> n;
	
	forn(i, n) cin >> c[i].ff >> c[i].se;
		
	forn(i, h + 1) forn(j, w + 1) {
		com[i][j] = -1;
		forn(k, 5) d[i][j][k] = inf;
	}
	queue<PR<int>> q;
	forn(k, n -1) {
		auto &[i, j] = c[k];
		if(com[i][j] == -1) {
			com[i][j] = 0;
			q.emplace(i, j);
		}
	}
	
	
	while(size(q)) {
		auto [i, j] = q.front();
		q.pop();
		for(auto [di, dj] : dir) {
			int x = di + i, y = j + dj;
			if(0 <= x && x <= h && 0 <= y && y <= w && com[x][y] == -1) {
				com[x][y] = com[i][j] + C;
				q.push({x, y});
			}
		}
	}
	com[c[n-1].ff][c[n-1].se] = 0;
	priority_queue<tuple<ll, int, int, int>> pq;
	d[c[0].ff][c[0].se][4] = 0;
	pq.push({0, c[0].ff, c[0].se, 4});
	auto upd = [&](int i, int j, int t, ll a) {
		if(0 <= i && i <= h && 0 <= j && j <= w && a < d[i][j][t]) {
			d[i][j][t] = a;
			pq.push({-a, i, j, t});
		}
	};
	
	while(!pq.empty()) {
		auto [s, i, j, t] = pq.top();
		pq.pop();
		s = -s;
		//debug(i, j, s);
		if(d[i][j][t] < s) continue;
		
		if(t == 4) {
			forn(p, 4) {
				int x = dir[p].ff + i, y = dir[p].se + j;
				upd(i, j, p, s+B);
				upd(x, y, 4, s+C);
			}
		}
		else {
			int x = dir[t].ff + i, y = dir[t].se + j;
			upd(x, y, t, s+A);
			upd(i, j, 4, s+com[i][j]);
		}
	}
	
	cout << d[c[n-1].ff][c[n-1].se][4] << '\n';
	
	
	
}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}
         
    

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65