oj.uz

Submission #100660

# Submission time Handle Problem Language Result Execution time Memory
100660 2019-03-13T05:45:51 Z cki86201 Round words (IZhO13_rowords) C++11
100 / 100
 206 ms 96772 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

char X[4020], Y[2040];
int N, M, ans;
int dp[4020][2040], pre[4020][2040], c[4020][2040];

void solve() {
	memset(dp, 0, sizeof dp);
	memset(pre, 0, sizeof pre);
	memset(c, 0, sizeof c);
	for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) {
		dp[i][j] = dp[i][j-1];
		if(dp[i-1][j-1] + 1 > dp[i][j] && X[i] == Y[j]) dp[i][j] = dp[i-1][j-1] + 1, pre[i][j] = 1;
		if(dp[i-1][j] > dp[i][j]) dp[i][j] = dp[i-1][j], pre[i][j] = 2;
	}
	for(int i=1;i<=N/2;i++) {
		int sum = 0;
		for(int j=1;j<=M;j++) sum += c[i+N/2-1][j];
		ans = max(ans, dp[i+N/2-1][M] + sum);
		int f = -1;
		for(int j=1;j<=M;j++) if(X[i] == Y[j]) {
			f = j; break;
		}
		if(f == -1) continue;
		pre[i][f] = 0; c[i][f]--;
		for(int j=i+1;j<=N;j++) {
			if(pre[j][f] != 2) {
				++f;
				while(f <= M && pre[j][f] == 0) ++f;
			}
			if(f > M) break;
			pre[j][f] = 0; c[j][f]--;
		}
	}
	
}

int main() {
	scanf("%s%s", X+1, Y+1);
	N = (int)strlen(X+1), M = (int)strlen(Y+1);
	for(int i=1;i<=N;i++) X[i+N] = X[i];
	N *= 2;
	solve();
	reverse(Y+1, Y+1+M);
	solve();
	printf("%d\n", ans);
	return 0;
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", X+1, Y+1);
  ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 96704 KB Output is correct
2 Correct 98 ms 96632 KB Output is correct
3 Correct 98 ms 96760 KB Output is correct
4 Correct 99 ms 96556 KB Output is correct
5 Correct 100 ms 96636 KB Output is correct
6 Correct 106 ms 96632 KB Output is correct
7 Correct 112 ms 96556 KB Output is correct
8 Correct 183 ms 96656 KB Output is correct
9 Correct 192 ms 96660 KB Output is correct
10 Correct 168 ms 96636 KB Output is correct
11 Correct 196 ms 96632 KB Output is correct
12 Correct 201 ms 96712 KB Output is correct
13 Correct 206 ms 96576 KB Output is correct
14 Correct 200 ms 96712 KB Output is correct
15 Correct 179 ms 96632 KB Output is correct
16 Correct 205 ms 96684 KB Output is correct
17 Correct 183 ms 96632 KB Output is correct
18 Correct 185 ms 96652 KB Output is correct
19 Correct 153 ms 96616 KB Output is correct
20 Correct 206 ms 96772 KB Output is correct
21 Correct 122 ms 96632 KB Output is correct
22 Correct 138 ms 96632 KB Output is correct
23 Correct 144 ms 96632 KB Output is correct
24 Correct 149 ms 96636 KB Output is correct
25 Correct 177 ms 96760 KB Output is correct