QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131588#4676. Amalgamated ArtichokesPetroTarnavskyi#WA 0ms3616kbC++171.8kb2023-07-27 18:08:522023-07-27 18:08:53

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-27 18:08:53]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2023-07-27 18:08:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 74;
const int MAX = 17474;
const int INF = 1e9 + 47;

int dp[MAX][N][N];
int mn[4][N][N];
char c[N][N];


void create(int l0, int dx, int l1, int dy, int t, int idx)
{
	FOR (i, 0, 50)
	{
		FOR (j, 0, 50)
		{
			int x = l0 + dx * i;
			int y = l1 + dy * j;
			mn[t][x][y] = dp[idx][x][y];
			int nx = x - dx;
			int ny = y - dy;
			if (nx >= 0 && nx <= 50) mn[t][x][y] = min(mn[t][x][y], mn[t][nx][y]);
			if (ny >= 0 && ny <= 50) mn[t][x][y] = min(mn[t][x][y], mn[t][x][ny]);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	FOR (i, 0, N) FOR (j, 0, N) c[i][j] = 'a';
	
	int n, m;
	cin >> n >> m;
	FOR (i, 0, n) FOR (j, 0, m) cin >> c[i][j];
	
	FOR (i, 0, N) FOR (j, 0, N) dp[0][i][j] = INF;
	dp[0][0][0] = 0;
	
	string s;
	cin >> s;
	FOR (step, 0, SZ(s))
	{
		create(0, 1, 0, 1, 0, step);
		create(0, 1, 49, -1, 1, step);
		create(49, -1, 0, 1, 2, step);
		create(49, -1, 49, -1, 3, step);
		FOR (i, 0, n)
		{
			FOR (j, 0, m)
			{
				if (c[i][j] == s[step])
				{
					dp[step + 1][i][j] = i + j + mn[0][i][j];
					dp[step + 1][i][j] = i - j + mn[1][i][j];
					dp[step + 1][i][j] = - i + j + mn[2][i][j];
					dp[step + 1][i][j] = - i - j + mn[3][i][j];
					
				}
				else
					dp[step + 1][i][j] = INF;
			}
		}
	}
	int ans = INF;
	FOR (i, 0, n) FOR (j, 0, m) ans = min(ans, dp[SZ(s)][i][j]);
	cout << ans << '\n';
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

42 1 23 4 8 10

output:

0

result:

wrong answer 1st numbers differ - expected: '104.8551105', found: '0.0000000', error = '1.0000000'