oj.uz

Submission #100654

# Submission time Handle Problem Language Result Execution time Memory
100654 2019-03-13T05:32:12 Z cki86201 Round words (IZhO13_rowords) C++11
76 / 100
 110 ms 69188 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;
int dp[4020][2040], pre[4020][2040], c[4020][2040];

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;
	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;
	}
	int ans = 0;
	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]--;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:37: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
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 632 KB Output isn't correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 1400 KB Output is correct
6 Correct 28 ms 24056 KB Output is correct
7 Correct 25 ms 16236 KB Output is correct
8 Incorrect 81 ms 44796 KB Output isn't correct
9 Correct 80 ms 46584 KB Output is correct
10 Correct 74 ms 47352 KB Output is correct
11 Correct 77 ms 52060 KB Output is correct
12 Correct 79 ms 50644 KB Output is correct
13 Correct 110 ms 57092 KB Output is correct
14 Correct 83 ms 54008 KB Output is correct
15 Correct 89 ms 59256 KB Output is correct
16 Correct 96 ms 49784 KB Output is correct
17 Incorrect 75 ms 54264 KB Output isn't correct
18 Correct 97 ms 66424 KB Output is correct
19 Correct 68 ms 47352 KB Output is correct
20 Incorrect 101 ms 58552 KB Output isn't correct
21 Correct 52 ms 46684 KB Output is correct
22 Correct 65 ms 53752 KB Output is correct
23 Correct 73 ms 57948 KB Output is correct
24 Incorrect 78 ms 61164 KB Output isn't correct
25 Incorrect 92 ms 69188 KB Output isn't correct