oj.uz

Submission #13599

# Submission time Handle Problem Language Result Execution time Memory
13599 2015-02-25T11:54:35 Z tncks0121 Round words (IZhO13_rowords) C++14
28 / 100
 266 ms 113400 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 r-th row */
		{
			int i = r;
			int j;
			for (j = 1; j <= M && par[r][j] != 1; j++);
			if (j > M) continue;
			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 if (par[i][j + 1] == 0) ++j;
				else break;
				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\n", ans);
	return 0;
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:45: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
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 33244 KB Output isn't correct
2 Correct 29 ms 33272 KB Output is correct
3 Correct 30 ms 33400 KB Output is correct
4 Correct 30 ms 33528 KB Output is correct
5 Incorrect 31 ms 33500 KB Output isn't correct
6 Correct 48 ms 42120 KB Output is correct
7 Correct 55 ms 49016 KB Output is correct
8 Incorrect 73 ms 49164 KB Output isn't correct
9 Incorrect 85 ms 49016 KB Output isn't correct
10 Incorrect 79 ms 49144 KB Output isn't correct
11 Incorrect 86 ms 50572 KB Output isn't correct
12 Correct 100 ms 52672 KB Output is correct
13 Incorrect 102 ms 52472 KB Output isn't correct
14 Incorrect 85 ms 51448 KB Output isn't correct
15 Incorrect 134 ms 52972 KB Output isn't correct
16 Incorrect 79 ms 50424 KB Output isn't correct
17 Incorrect 96 ms 51096 KB Output isn't correct
18 Correct 111 ms 55416 KB Output is correct
19 Incorrect 76 ms 48988 KB Output isn't correct
20 Incorrect 96 ms 53112 KB Output isn't correct
21 Incorrect 105 ms 49016 KB Output isn't correct
22 Runtime error 219 ms 103416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 229 ms 106360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 237 ms 108792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 266 ms 113400 KB Execution killed with signal 11 (could be triggered by violating memory limits)