oj.uz

Submission #13607

# Submission time Handle Problem Language Result Execution time Memory
13607 2015-02-25T12:15:26 Z tncks0121 Round words (IZhO13_rowords) C++14
0 / 100
 167 ms 113228 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int Z = 2050;

int N, M;
char S[Z], T[Z];

const int dx[] = { 0, -1, -1 };
const int dy[] = { -1, -1, 0 };

int tb[Z + Z][Z];
int par[Z + Z][Z];

int ans;

int main() {

	scanf("%s%s", S + 1, T + 1);
	N = strlen(S + 1);
	M = strlen(T + 1);
	for (int i = N + 1; i <= N + N; i++) S[i] = S[i - N];

	memset(par, -1, sizeof par);

	for (int i = 1; i <= N + N; i++) par[i][0] = 2;
	for (int j = 1; j <= M; j++) par[0][j] = 0;
	for (int i = 1; i <= N + N; i++) {
		for (int j = 1; j <= M; j++) {
			int cands[] = {
				tb[i][j - 1],
				tb[i - 1][j - 1] + (S[i] == T[j]),
				tb[i - 1][j]
			};
			tb[i][j] = *max_element(cands, cands + 3);
			par[i][j] = max_element(cands, cands + 3) - cands;
		}
	}

	for (int r = 1; r <= N; r++) {
		// drop the first row
		{
			int i = r;
			int j;
			for (j = 1; j <= M && par[r][j] != 1; j++);
			if (j <= M) {
				par[i][j] = 0;

				while (i < N + N && j <= M) {
					if (par[i + 1][j] == 2) ++i;
					else if (j == M) break;
					else if (par[i + 1][j + 1] == 1) ++i, ++j;
					else ++j;
					par[i][j] = 0;
				}
			}
		}

		// calc answer
		{
			int ret = 0;
			for (int i = N + r, j = M; i > r && j > 0;) {
				int d = par[i][j];
				if (d == 1) ++ret;
				i += dx[d]; j += dy[d];
			}
			ans = max(ans, ret);
			printf("%d %d\n", r, ret);
		}
	}

	printf("%d\n", ans);
	return 0;
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", S + 1, T + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 33272 KB Output isn't correct
2 Incorrect 30 ms 33296 KB Output isn't correct
3 Incorrect 29 ms 33400 KB Output isn't correct
4 Incorrect 30 ms 33656 KB Output isn't correct
5 Incorrect 30 ms 33528 KB Output isn't correct
6 Incorrect 51 ms 41976 KB Output isn't correct
7 Incorrect 63 ms 49016 KB Output isn't correct
8 Incorrect 111 ms 48988 KB Output isn't correct
9 Incorrect 117 ms 49016 KB Output isn't correct
10 Incorrect 105 ms 49016 KB Output isn't correct
11 Runtime error 134 ms 102180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 134 ms 105976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 142 ms 105972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 136 ms 103544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 141 ms 107036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 134 ms 101880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 145 ms 103160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 151 ms 111864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Incorrect 95 ms 49108 KB Output isn't correct
20 Runtime error 146 ms 107444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 144 ms 98800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 151 ms 103416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 158 ms 106436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 158 ms 108788 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 167 ms 113228 KB Execution killed with signal 11 (could be triggered by violating memory limits)