oj.uz

Submission #483125

# Submission time Handle Problem Language Result Execution time Memory
483125 2021-10-27T19:05:35 Z kaxzert Round words (IZhO13_rowords) C++17
40 / 100
 2000 ms 11084 KB 
/**
      00  00      11      00  00  111111  00000  111111  000000
      00 00      1111      0000      11   00     11  11  000000
      0000      11  11      00      11    00000  111111    00
      00 00    11111111    0000    11     00     11 11     00
      00  00  11      11  00  00  111111  00000  11  11    00
**/

#include<bits/stdc++.h>

using namespace std;

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)

void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}

#ifdef TAP
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...) 
#endif

void setIO(string s) {
    if (sz(s) != 0) {
        freopen((s+".inp").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

void setIOusaco(string s) {
    if (sz(s) != 0) {
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

int lcs(string a, string b) {
	b += b;
	vt<vt<int> > f(sz(a)+1, vt<int>(sz(b)+1, 0));

	int res = 0;
	fto(j, 0, sz(b)/2 - 1) {
		fto(i, 0, sz(a)-1) {
			fto(k, 0, sz(b)/2 - 1) {
				if (a[i] == b[k+j]) f[i+1][k+1] = f[i][k]+1;
				else f[i+1][k+1] = max(f[i+1][k], f[i][k+1]);
			}
		}
		res = max(res, f[sz(a)][sz(b)/2]);
	} 
	return res;
}

int main() {
    #ifndef TAP 
    //setIO("roundword2013");
    //setIOusaco("roundword2013");
    #endif

    fast;
    string s, t;
    cin >> s >> t;
    int ans1 = lcs(s, t);
    reverse(all(t));
    int ans2 = lcs(s, t);

    cout << max(ans1, ans2) << '\n';

    return 0;
}

Compilation message

rowords.cpp: In function 'void setIO(std::string)':
rowords.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen((s+".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp: In function 'void setIOusaco(std::string)':
rowords.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 34 ms 1128 KB Output is correct
7 Execution timed out 2074 ms 8140 KB Time limit exceeded
8 Execution timed out 2094 ms 8176 KB Time limit exceeded
9 Execution timed out 2089 ms 8176 KB Time limit exceeded
10 Execution timed out 2079 ms 8140 KB Time limit exceeded
11 Execution timed out 2056 ms 8908 KB Time limit exceeded
12 Execution timed out 2067 ms 10412 KB Time limit exceeded
13 Execution timed out 2086 ms 10316 KB Time limit exceeded
14 Execution timed out 2081 ms 9244 KB Time limit exceeded
15 Execution timed out 2082 ms 11084 KB Time limit exceeded
16 Execution timed out 2092 ms 9000 KB Time limit exceeded
17 Execution timed out 2099 ms 6836 KB Time limit exceeded
18 Execution timed out 2091 ms 10572 KB Time limit exceeded
19 Execution timed out 2091 ms 8140 KB Time limit exceeded
20 Execution timed out 2093 ms 9500 KB Time limit exceeded
21 Correct 179 ms 2400 KB Output is correct
22 Correct 512 ms 3896 KB Output is correct
23 Correct 1098 ms 5420 KB Output is correct
24 Correct 1173 ms 5580 KB Output is correct
25 Execution timed out 2066 ms 7436 KB Time limit exceeded