oj.uz

Submission #483457

# Submission time Handle Problem Language Result Execution time Memory
483457 2021-10-29T15:17:07 Z XII Round words (IZhO13_rowords) C++17
100 / 100
 178 ms 63000 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "rowords"
void Fi(){
    if(fopen(PROB".in", "r")){
        freopen(PROB".in", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 2e3 + 1;
int dp[N * 2][N], t[N * 2][N];
int n, m, ans;
string s, p;

const int dx[] = {0, -1, -1};
const int dy[] = {-1, -1, 0};

void calc(){
    memset(dp, 0, sizeof(dp));
    memset(t, -1, sizeof(t));
    FORU(i, 1, n * 2) t[i][0] = 2;
    FORU(j, 1, m) t[0][j] = 0;
    FORU(i, 1, n * 2) FORU(j, 1, m){
        auto selection = {
            dp[i][j - 1],
            dp[i - 1][j - 1] + (s[i] == p[j]),
            dp[i - 1][j]
        };
        dp[i][j] = *max_element(ALL(selection));
        t[i][j] = max_element(ALL(selection)) - selection.begin();
    }
    ans = max(ans, dp[n][m]);
    FORU(row, 1, n){
        {
            int i = row, j;
            for(j = 1; j <= m && t[i][j] != 1; ++j);
            if(j <= m){
                t[i][j] = 0;
                while(i < n * 2 && j <= m){
                    if(t[i + 1][j] == 2) t[++i][j] = 0;
                    else if(j == m) break;
                    else if(t[i + 1][j + 1] == 1) t[++i][++j] = 0;
                    else ++j;
                }
            }
        }
        {
            int tmp = 0;
            for(int i = n + row, j = m; i > row && j > 0;){
                int d = t[i][j];
                if(d == 1) ++tmp;
                i += dx[d], j += dy[d];
            }
            ans = max(ans, tmp);
        }
    }
}

int main(){
    IOS;
    Fi();
    cin >> s >> p;
    n = s.size(), m = p.size();
    s = " " + s + s;
    p = " " + p;
    calc();
    reverse(p.begin() + 1, p.begin() + m + 1);
    calc();
    cout << ans;
    return 0;
}

Compilation message

rowords.cpp: In function 'void Fi()':
rowords.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
rowords.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62924 KB Output is correct
2 Correct 36 ms 62924 KB Output is correct
3 Correct 33 ms 62876 KB Output is correct
4 Correct 36 ms 62916 KB Output is correct
5 Correct 33 ms 62920 KB Output is correct
6 Correct 43 ms 62908 KB Output is correct
7 Correct 59 ms 62924 KB Output is correct
8 Correct 99 ms 62976 KB Output is correct
9 Correct 110 ms 62976 KB Output is correct
10 Correct 101 ms 62924 KB Output is correct
11 Correct 106 ms 62928 KB Output is correct
12 Correct 86 ms 62924 KB Output is correct
13 Correct 144 ms 62988 KB Output is correct
14 Correct 117 ms 62984 KB Output is correct
15 Correct 142 ms 63000 KB Output is correct
16 Correct 117 ms 62960 KB Output is correct
17 Correct 119 ms 62984 KB Output is correct
18 Correct 152 ms 62980 KB Output is correct
19 Correct 97 ms 62924 KB Output is correct
20 Correct 153 ms 62924 KB Output is correct
21 Correct 104 ms 62932 KB Output is correct
22 Correct 130 ms 62980 KB Output is correct
23 Correct 141 ms 62984 KB Output is correct
24 Correct 160 ms 62988 KB Output is correct
25 Correct 178 ms 62892 KB Output is correct