oj.uz

Submission #124932

# Submission time Handle Problem Language Result Execution time Memory
124932 2019-07-04T07:35:17 Z 구재현(#3056) Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 370 ms 106360 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++){
			sx[i + lcp[i][j]][j] = min(sx[i + lcp[i][j]][j], i);
			sy[i][lcp[i][j] + j] = min(sy[i][lcp[i][j] + j], j);
		}
	}
	dap ret = {-1, -1, -1};
	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]);
			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 73 ms 71544 KB Output is correct
2 Correct 73 ms 71416 KB Output is correct
3 Correct 72 ms 71288 KB Output is correct
4 Correct 73 ms 71416 KB Output is correct
5 Correct 73 ms 71544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 71544 KB Output is correct
2 Correct 73 ms 71416 KB Output is correct
3 Correct 72 ms 71288 KB Output is correct
4 Correct 73 ms 71416 KB Output is correct
5 Correct 73 ms 71544 KB Output is correct
6 Correct 78 ms 73208 KB Output is correct
7 Correct 78 ms 73268 KB Output is correct
8 Correct 79 ms 73160 KB Output is correct
9 Correct 79 ms 73080 KB Output is correct
10 Correct 79 ms 73240 KB Output is correct
11 Correct 78 ms 73208 KB Output is correct
12 Correct 78 ms 73116 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 71544 KB Output is correct
2 Correct 73 ms 71416 KB Output is correct
3 Correct 72 ms 71288 KB Output is correct
4 Correct 73 ms 71416 KB Output is correct
5 Correct 73 ms 71544 KB Output is correct
6 Correct 78 ms 73208 KB Output is correct
7 Correct 78 ms 73268 KB Output is correct
8 Correct 79 ms 73160 KB Output is correct
9 Correct 79 ms 73080 KB Output is correct
10 Correct 79 ms 73240 KB Output is correct
11 Correct 78 ms 73208 KB Output is correct
12 Correct 78 ms 73116 KB Output is correct
13 Correct 366 ms 106360 KB Output is correct
14 Correct 349 ms 106232 KB Output is correct
15 Correct 355 ms 105164 KB Output is correct
16 Correct 352 ms 106232 KB Output is correct
17 Correct 370 ms 105720 KB Output is correct
18 Correct 348 ms 106232 KB Output is correct
19 Correct 344 ms 106232 KB Output is correct
20 Correct 351 ms 105720 KB Output is correct
21 Correct 352 ms 105848 KB Output is correct