oj.uz

Submission #124930

# Submission time Handle Problem Language Result Execution time Memory
124930 2019-07-04T07:30:08 Z 구재현(#3056) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 420 ms 106396 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
using lint = long long;
using pi = pair<int, int>;

struct dap{
	int x, y, z;
	bool operator<(const dap &d)const{
		return z < d.z;
	}
};

int n, m;
string s, t;
int lcp[MAXN][MAXN];
int sx[MAXN][MAXN];
int sy[MAXN][MAXN];

dap solve(){
	for(int i=n-1; i>=0; i--){
		for(int j=m-1; j>=0; j--){
			if(s[i] == t[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
			else lcp[i][j] = 0;
		}
	}
	memset(sx, 0x3f, sizeof(sx));
	memset(sy, 0x3f, sizeof(sy));
	for(int i=0; i<=n; i++){
		for(int j=0; j<=m; j++){
			sy[i][lcp[i][j] + j] = min(sy[i][lcp[i][j] + j], j);
			sx[i + lcp[i][j]][j] = min(sx[i + lcp[i][j]][j], i);
		}
	}
	for(int i=n; i>=0; i--){
		for(int j=m; j>=0; j--){
			sx[i][j] = min(sx[i][j], sx[i+1][j]);
			sy[i][j] = min(sy[i][j], sy[i][j+1]);
		}
	}
	dap ret = {-1, -1, -1};
	for(int i=0; i<=n; i++){
		for(int j=0; j<=m; j++){
			int minsx = sx[i][j];
			int minsy = sy[i][j];
			ret = max(ret, (dap){minsx, minsy, i + j - minsx - minsy});
		}
	}
	return ret;
}

int main(){
	cin >> s >> t;
	n = s.size();
	m = t.size();
	auto ret = solve();
	reverse(t.begin(), t.end());
	auto y = solve();
	y.y = m - y.y - y.z;
	ret = max(ret, y);
	cout << ret.z << endl;
	cout << ret.x << " " << ret.y << endl;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 71544 KB Output is correct
2 Correct 73 ms 71420 KB Output is correct
3 Correct 73 ms 71416 KB Output is correct
4 Correct 72 ms 71416 KB Output is correct
5 Correct 73 ms 71360 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 71544 KB Output is correct
2 Correct 73 ms 71420 KB Output is correct
3 Correct 73 ms 71416 KB Output is correct
4 Correct 72 ms 71416 KB Output is correct
5 Correct 73 ms 71360 KB Output is correct
6 Correct 79 ms 73208 KB Output is correct
7 Correct 82 ms 73208 KB Output is correct
8 Correct 80 ms 73208 KB Output is correct
9 Correct 79 ms 73208 KB Output is correct
10 Correct 80 ms 73208 KB Output is correct
11 Correct 80 ms 73208 KB Output is correct
12 Correct 80 ms 73336 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 71544 KB Output is correct
2 Correct 73 ms 71420 KB Output is correct
3 Correct 73 ms 71416 KB Output is correct
4 Correct 72 ms 71416 KB Output is correct
5 Correct 73 ms 71360 KB Output is correct
6 Correct 79 ms 73208 KB Output is correct
7 Correct 82 ms 73208 KB Output is correct
8 Correct 80 ms 73208 KB Output is correct
9 Correct 79 ms 73208 KB Output is correct
10 Correct 80 ms 73208 KB Output is correct
11 Correct 80 ms 73208 KB Output is correct
12 Correct 80 ms 73336 KB Output is correct
13 Correct 420 ms 106396 KB Output is correct
14 Correct 410 ms 106360 KB Output is correct
15 Correct 408 ms 105208 KB Output is correct
16 Correct 406 ms 106268 KB Output is correct
17 Correct 390 ms 105720 KB Output is correct
18 Correct 401 ms 106104 KB Output is correct
19 Correct 398 ms 106184 KB Output is correct
20 Correct 404 ms 105720 KB Output is correct
21 Correct 417 ms 105948 KB Output is correct