Submission #143345

#	Time	Username	Problem	Language	Result	Execution time	Memory
143345		godwind	Soccer (JOI17_soccer)	C++14	100 / 100	1022 ms	27432 KiB

soccer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                        
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                        
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define ghost signed
#define left left228
#define right right228
#define complex complex228
#define count count228
#define sin sin228
#define list list228

const int N = 505;
const int M = 100 * 1000 + 228;
const long long INF = 1e18 + 228;

long long h, w, A, B, C, n;
long long dp[N][N][4][2];
long long near[N][N];

struct pt
{
	int x, y;
	pt() {}
	pt(int _x, int _y) {x = _x, y = _y;}
};
struct state
{
	int x, y, dir, is;
	state() {}
	state(int _x, int _y, int _dir, int _is) {x = _x, y = _y, dir = _dir, is = _is;}
};
bool operator<(state fir, state sec) { return dp[fir.x][fir.y][fir.dir][fir.is] > dp[sec.x][sec.y][sec.dir][sec.is]; }
pt p[M];
vector< pair<int, int> > dirs;
void iiiiiiiiiiiiiiiiiiii() {
	dirs.emplace_back(0, 1);
	dirs.emplace_back(0, -1);
	dirs.emplace_back(1, 0);
	dirs.emplace_back(-1, 0);
}

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	iiiiiiiiiiiiiiiiiiii();
	cin >> h >> w >> A >> B >> C >> n;
	for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
	{
		for (int i = 0; i <= h; ++i) {
			for (int j = 0; j <= w; ++j) near[i][j] = INF;
		}
		vector< pt > q;
		for (int i = 1; i <= n; ++i) q.emplace_back(p[i].x, p[i].y), near[p[i].x][p[i].y] = 0;
		for (int it = 0; it < (int)q.size(); ++it) {
			pt ppp = q[it];
			int x = ppp.x, y = ppp.y;
			for (int dx = -1; dx <= 1; ++dx) {
				for (int dy = -1; dy <= 1; ++dy) {
					if (abs(dx) == abs(dy)) continue;
					int nx = x + dx, ny = y + dy;
					if (!(0 <= nx && nx <= h && 0 <= ny && ny <= w)) continue;
					if (near[x][y] + 1 < near[nx][ny]) {
						near[nx][ny] = near[x][y] + 1;
						q.emplace_back(nx, ny);
					}
				}
			}
		}
	}
	for (int i = 0; i <= h; ++i) {
		for (int j = 0; j <= w; ++j) {
			for (int dir = 0; dir < 4; ++dir) {
				for (int is = 0; is < 2; ++is) dp[i][j][dir][is] = INF;
			}
		}
	}
	dp[p[1].x][p[1].y][0][1] = 0;
	priority_queue< state > q;
	q.push(state(p[1].x, p[1].y, 0, 1));
	while (!q.empty()) {
		state f = q.top(); q.pop();
		int x = f.x, y = f.y, dir = f.dir, is = f.is;
		long long D = dp[x][y][dir][is];
		if (is) {
			for (int dr = 0; dr < 4; ++dr) {
				int nx = x + dirs[dr].first, ny = y + dirs[dr].second;
				if (!(0 <= nx && nx <= h && 0 <= ny && ny <= w)) continue;
				if (D + C < dp[nx][ny][0][1]) {
					dp[nx][ny][0][1] = D + C;
					q.push(state(nx, ny, 0, 1));
				}
				if (D + A + B < dp[nx][ny][dr][0]) {
					dp[nx][ny][dr][0] = D + A + B;
					q.push(state(nx, ny, dr, 0));
				}
			}
		} else {
			int nx = x + dirs[dir].first, ny = y + dirs[dir].second;
			if (0 <= nx && nx <= h && 0 <= ny && ny <= w) {
				if (D + A < dp[nx][ny][dir][0]) {
					dp[nx][ny][dir][0] = D + A;
					q.push(state(nx, ny, dir, 0));
				}
			}
			if (D + near[x][y] * C < dp[x][y][0][1]) {
				dp[x][y][0][1] = D + near[x][y] * C;
				q.push(state(x, y, 0, 1));
			}
		}
	}
	long long res = INF;
	for (int dir = 0; dir < 4; ++dir) uin(res, dp[p[n].x][p[n].y][dir][1]), uin(res, dp[p[n].x][p[n].y][dir][0]);
	cout << res << '\n';
    return 0;
} // kek ;
// Ого! Кажетсья это $#@!
 

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