oj.uz

답안 #1079839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1079839 2024-08-29T02:25:47 Z chaoslong 원형 문자열 (IZhO13_rowords) C++14
24 / 100
 2000 ms 6044 KB 
// Calm down.
// Think three times, code twice.
#include "bits/stdc++.h"
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int N = 2005;
const int mod = 1e9 + 7; // 998244353
const ll oo = 1e18;

int dp[N][N];
string s1, s2;

void to_nho_cau() {
    cin >> s1 >> s2;
    int n = s1.length(), m = s2.length();
    s1 = ' ' + s1; s2 = ' ' + s2;
    int ans = 0;
    forr(s, 1, n) {
        string temp = "";
        forr(i, s, n) temp = temp + s1[i];
        forr(i, 1, s-1) temp = temp + s1[i];
        temp = ' ' + temp;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
//        cout << temp << "\n";
        forr(i, 1, n) {
            forr(j, 1, m) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                if(temp[i] == s2[j]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
            }
        }
        ans = max(ans, dp[n][m]);
    }
    cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef LOCAL
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) to_nho_cau();
}
/*
1.self check:
2.long long
3.size of array
4.code for testing
5.initializing
6.modulo number
*/
/**
  ∧__∧
（｀•ω• )づ__∧
（つ　 /( •ω•。)
  しーＪ (nnノ) pat pat
**/
/**  /\_/\
*   (= ._.)
*   / >☕ \>💻
**/
/**
･*･  ∧,,∧ ∧_∧   ･*･
'.　 ( ｡･ω･)(･ω･｡ )　  .'
　'･ |   つ♥と    |.･'
      *'***** '*
**/

Compilation message

rowords.cpp:78:9: warning: "/*" within comment [-Wcomment]
   78 | /**  /\_/\
      |

Subtask #1
24.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 473 ms 1292 KB Output is correct
7 Execution timed out 2007 ms 4700 KB Time limit exceeded
8 Execution timed out 2064 ms 4528 KB Time limit exceeded
9 Execution timed out 2041 ms 4604 KB Time limit exceeded
10 Execution timed out 2043 ms 4596 KB Time limit exceeded
11 Execution timed out 2074 ms 4960 KB Time limit exceeded
12 Execution timed out 2089 ms 5772 KB Time limit exceeded
13 Execution timed out 2044 ms 5660 KB Time limit exceeded
14 Execution timed out 2047 ms 5380 KB Time limit exceeded
15 Execution timed out 2064 ms 6044 KB Time limit exceeded
16 Execution timed out 2040 ms 5068 KB Time limit exceeded
17 Execution timed out 2061 ms 3932 KB Time limit exceeded
18 Execution timed out 2044 ms 5784 KB Time limit exceeded
19 Execution timed out 2092 ms 4624 KB Time limit exceeded
20 Execution timed out 2044 ms 5212 KB Time limit exceeded
21 Correct 1721 ms 1796 KB Output is correct
22 Execution timed out 2031 ms 2480 KB Time limit exceeded
23 Execution timed out 2028 ms 3256 KB Time limit exceeded
24 Execution timed out 2057 ms 3532 KB Time limit exceeded
25 Execution timed out 2033 ms 4268 KB Time limit exceeded