Submission #646421

#	Time	Username	Problem	Language	Result	Execution time	Memory
646421		dozer	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	17 / 85	47 ms	35620 KiB

necklace

#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 (stderr)

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 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40