oj.uz

Submission #124964

# Submission time Handle Problem Language Result Execution time Memory
124964 2019-07-04T08:21:48 Z 이온조(#3049) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
0 / 85
 4 ms 1400 KB 
#include <bits/stdc++.h>
using namespace std;

char A[3009], B[3009];
int N, M, ans, AI, BI, L[3009][3009], R[3009][3009];

int GL(int i, int j) {
	if(i <= 1 || j >= M) {
		if(A[i] != B[j]) return 0;
		return 1;
	}
	if(L[i][j] != -1) return L[i][j];
	if(A[i] == B[j]) L[i][j] = 1;
	else L[i][j] = 0;
	if(A[i] == B[j + GL(i-1, j)]) L[i][j] = max(L[i][j], GL(i-1, j) + 1);
	if(A[i - GL(i, j+1)] == B[j]) L[i][j] = max(L[i][j], GL(i, j+1) + 1);
}

int GR(int i, int j) {
	if(i >= N || j <= 1) {
		if(A[i] != B[j]) return 0;
		return 1;
	}
	if(R[i][j] != -1) return R[i][j];
	if(A[i] == B[j]) R[i][j] = 1;
	else R[i][j] = 0;
	if(A[i] == B[j - GR(i+1, j)]) R[i][j] = max(R[i][j], GR(i+1, j) + 1);
	if(A[i + GR(i, j-1)] == B[j]) R[i][j] = max(R[i][j], GR(i, j-1) + 1);
}

void solve(int x) {
	for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) L[i][j] = R[i][j] = -1;
	for(int i=0; i<=N; i++) {
		for(int j=0; j<=M; j++) {
			int vl = (GL(i, j+1) < 0 ? 0 : GL(i, j+1)), vr = (GR(i+1, j) < 0 ? 0 : GR(i+1, j));
			int v = vl + vr;
			if(ans < v) {
				ans = v;
				AI = i - vl + 1;
				if(x) BI = M - (j + vr) + 1;
				else BI = j - vr + 1;
			}
		}
	}
}

int main() {
	scanf("%s %s", A+1, B+1);
	N = strlen(A+1), M = strlen(B+1);
	A[0] = A[N+1] = '?'; B[0] = B[M+1] = '!';
	solve(0);
	reverse(B, B+M+2);
	solve(1);
	printf("%d\n%d %d", ans, AI - 1, BI - 1);
	return 0;
}

Compilation message

necklace.cpp: In function 'int GL(int, int)':
necklace.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
necklace.cpp: In function 'int GR(int, int)':
necklace.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
necklace.cpp: In function 'int main()':
necklace.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s %s", A+1, B+1);
  ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -