oj.uz

Submission #646421

# Submission time Handle Problem Language Result Execution time Memory
646421 2022-09-29T18:45:34 Z dozer Necklace (Subtask 1-3) (BOI19_necklace1) C++14
17 / 85
 47 ms 35620 KB 
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 3005

int dp[N][N];
const int INF = 1e9 + 7;

pair<int, pii> f(string s, string t)
{
	int n = s.size(), m = t.size();
	for (int i = n; i >= 1; i--)
	{
		for (int j = m; j >= 1; j--)
		{
			int t1 = 0;
			if (s[i - 1] == t[j - 1]) t1 = dp[i + 1][j + 1] + 1;
			dp[i][j] = t1;
		}
	}

	int maks = 0, x = 0, y = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (maks < dp[i][j])
			{
				maks = dp[i][j];
				x = i - 1;
				y = j - 1;
			}
		}
	}
	return {maks, {x, y}};
}

int32_t main()
{
	fastio();

	string s, t;
	cin>>s>>t;
	int n = s.size(), m = t.size();

	pair<int, pii> tmp = f(s, t);
	
	reverse(s.begin(), s.end());
	pair<int, pii> tmp2 = f(s, t);
	if (tmp.st < tmp2.st)
	{
		//cout<<tmp2.nd.st<<sp<<tmp2.nd.nd<<endl;
		int l = tmp2.st;
		tmp.st = l;
		tmp.nd.st = (n - 1) - tmp2.nd.st - l + 1;
		tmp.nd.nd = tmp2.nd.nd;	
	}
	cout<<tmp.st<<endl;
	cout<<tmp.nd.st<<sp<<tmp.nd.nd<<endl;


	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<"seconds\n";
}

Compilation message

necklace.cpp: In function 'int32_t main()':
necklace.cpp:51:20: warning: unused variable 'm' [-Wunused-variable]
   51 |  int n = s.size(), m = t.size();
      |                    ^

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 724 KB Output is partially correct
2 Partially correct 1 ms 724 KB Output is partially correct
3 Partially correct 1 ms 596 KB Output is partially correct
4 Partially correct 1 ms 724 KB Output is partially correct
5 Partially correct 1 ms 724 KB Output is partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 724 KB Output is partially correct
2 Partially correct 1 ms 724 KB Output is partially correct
3 Partially correct 1 ms 596 KB Output is partially correct
4 Partially correct 1 ms 724 KB Output is partially correct
5 Partially correct 1 ms 724 KB Output is partially correct
6 Partially correct 2 ms 2516 KB Output is partially correct
7 Partially correct 2 ms 2516 KB Output is partially correct
8 Partially correct 2 ms 2388 KB Output is partially correct
9 Partially correct 2 ms 2388 KB Output is partially correct
10 Partially correct 3 ms 2516 KB Output is partially correct
11 Partially correct 2 ms 2516 KB Output is partially correct
12 Partially correct 2 ms 2376 KB Output is partially correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 724 KB Output is partially correct
2 Partially correct 1 ms 724 KB Output is partially correct
3 Partially correct 1 ms 596 KB Output is partially correct
4 Partially correct 1 ms 724 KB Output is partially correct
5 Partially correct 1 ms 724 KB Output is partially correct
6 Partially correct 2 ms 2516 KB Output is partially correct
7 Partially correct 2 ms 2516 KB Output is partially correct
8 Partially correct 2 ms 2388 KB Output is partially correct
9 Partially correct 2 ms 2388 KB Output is partially correct
10 Partially correct 3 ms 2516 KB Output is partially correct
11 Partially correct 2 ms 2516 KB Output is partially correct
12 Partially correct 2 ms 2376 KB Output is partially correct
13 Partially correct 45 ms 35620 KB Output is partially correct
14 Partially correct 47 ms 35620 KB Output is partially correct
15 Partially correct 45 ms 34360 KB Output is partially correct
16 Partially correct 42 ms 35480 KB Output is partially correct
17 Partially correct 44 ms 34900 KB Output is partially correct
18 Partially correct 46 ms 35492 KB Output is partially correct
19 Partially correct 47 ms 35412 KB Output is partially correct
20 Partially correct 43 ms 34960 KB Output is partially correct
21 Partially correct 44 ms 35148 KB Output is partially correct