oj.uz

Submission #143343

# Submission time Handle Problem Language Result Execution time Memory
143343 2019-08-13T17:30:41 Z godwind Soccer (JOI17_soccer) C++17
5 / 100
 3000 ms 20524 KB 
#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;
	queue<state> q;
	q.push(state(p[1].x, p[1].y, 0, 1));
	while (!q.empty()) {
		state f = q.front(); 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6668 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 121 ms 18324 KB Output is correct
4 Correct 319 ms 18756 KB Output is correct
5 Correct 26 ms 8976 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 18984 KB Output is correct
2 Correct 627 ms 18988 KB Output is correct
3 Correct 501 ms 15192 KB Output is correct
4 Correct 525 ms 18576 KB Output is correct
5 Correct 485 ms 17588 KB Output is correct
6 Execution timed out 3021 ms 20524 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6668 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 121 ms 18324 KB Output is correct
4 Correct 319 ms 18756 KB Output is correct
5 Correct 26 ms 8976 KB Output is correct
6 Correct 656 ms 18984 KB Output is correct
7 Correct 627 ms 18988 KB Output is correct
8 Correct 501 ms 15192 KB Output is correct
9 Correct 525 ms 18576 KB Output is correct
10 Correct 485 ms 17588 KB Output is correct
11 Execution timed out 3021 ms 20524 KB Time limit exceeded
12 Halted 0 ms 0 KB -