oj.uz

Submission #66483

# Submission time Handle Problem Language Result Execution time Memory
66483 2018-08-10T20:30:24 Z Benq Round words (IZhO13_rowords) C++11
100 / 100
 129 ms 26876 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

pi dp[2001][4001];
string A,B;
 
void init() {
    FOR(i,1,sz(A)+1) FOR(j,1,sz(B)+1) {
        pi bes = {-1,-1};
        bes = max(bes,{dp[i-1][j].f,0});
        bes = max(bes,{dp[i-1][j-1].f+(A[i-1] == B[j-1]),-1});
        bes = max(bes,{dp[i][j-1].f,-2});
        dp[i][j] = {bes.f,-bes.s};
    }
}
 
void adjust(int col) {
    int x = 1;
    while (x <= sz(A) && dp[x][col].s == 0) x++;
    if (x > sz(A)) return;
    
    dp[x][col].s = 0;
    pi cur = {x,col};
    while (cur.f <= sz(A) && cur.s <= sz(B)) {
        if (cur.s < sz(B) && dp[cur.f][cur.s+1].s == 2) {
            cur.s ++;
            dp[cur.f][cur.s].s = 0;
        } else if (cur.f < sz(A) && cur.s < sz(B) && dp[cur.f+1][cur.s+1].s == 1) {
            cur.f ++, cur.s ++;
            dp[cur.f][cur.s].s = 0;
        } else cur.f ++;
    }
}

int get(pi x) {
    int lo = x.s-sz(B)/2;
    int ret = 0;
    while (x.f && x.s > lo) {
        if (dp[x.f][x.s].s == 0) x.f --;
        else if (dp[x.f][x.s].s == 1) ret ++, x.f --, x.s --;
        else x.s --;
    }
    return ret;
}

int solve(string a, string b) {
    A = a, B = b+b;
    init();
    int ans = 0;
    F0R(i,sz(b)) {
        ans = max(ans,get({sz(a),i+sz(b)}));
        adjust(i+1);
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string a,b; cin >> a >> b;
    int ans = solve(a,b);
    reverse(all(a));
    ans = max(ans,solve(a,b));
    cout << ans;
}
 

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 13 ms 5880 KB Output is correct
7 Correct 63 ms 20088 KB Output is correct
8 Correct 99 ms 19976 KB Output is correct
9 Correct 112 ms 20088 KB Output is correct
10 Correct 82 ms 19960 KB Output is correct
11 Correct 87 ms 22008 KB Output is correct
12 Correct 65 ms 25212 KB Output is correct
13 Correct 129 ms 25356 KB Output is correct
14 Correct 100 ms 22904 KB Output is correct
15 Correct 118 ms 26744 KB Output is correct
16 Correct 116 ms 21880 KB Output is correct
17 Correct 67 ms 19064 KB Output is correct
18 Correct 113 ms 26876 KB Output is correct
19 Correct 80 ms 20088 KB Output is correct
20 Correct 116 ms 24060 KB Output is correct
21 Correct 23 ms 11256 KB Output is correct
22 Correct 36 ms 14712 KB Output is correct
23 Correct 50 ms 17528 KB Output is correct
24 Correct 55 ms 18424 KB Output is correct
25 Correct 79 ms 22520 KB Output is correct