oj.uz

Submission #338264

# Submission time Handle Problem Language Result Execution time Memory
338264 2020-12-22T20:20:59 Z souvenir_vayne Bajka (COCI20_bajka) C++14
70 / 70
 70 ms 1004 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <chrono>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define int long long
#define endl '\n'
#define ll long long
#define f first
#define fin cin
#define fout cout
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
#define all(x) x.begin(), x.end()
#define left vadia
#define lb lower_bound
#define right puta
using namespace std;
using namespace __gnu_pbds;
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str( ),"w",stdout);
}
typedef pair<ll, ll> pii;
typedef vector<vector<char>> mat;
typedef pair<int, string> pis;
const ll mod = 1e9+7;
typedef vector<int> vi;
typedef pair<int, pair<int, int>> piii;

int n, m, dp[305][305];
string s, t;

int solve(int i, int j) {

    if(j == t.size())
        return 0;
    if(dp[i][j] != -1)
        return dp[i][j];

    dp[i][j] = INF;
    if(i && s[i-1] == t[j])
        dp[i][j] = solve(i-1, j+1) + 1;
    if(i + 1 < n && s[i+1] == t[j])
        dp[i][j] = min(dp[i][j], solve(i+1, j+1) + 1);

    for(int nxt = 0; nxt < n; nxt++) {

        if(nxt == i) continue;
        if(s[nxt] == s[i] && nxt && s[nxt-1] == t[j])
            dp[i][j] = min(dp[i][j], solve(nxt-1, j+1) + abs(nxt  - i) + 1);
        if(s[nxt] == s[i] && nxt + 1 < n && s[nxt+1] == t[j])
            dp[i][j] = min(dp[i][j], solve(nxt+1, j+1) + abs(nxt  - i) + 1);

    }

    return dp[i][j];

}

int32_t main() {

    cin >> n >> m;
    cin >> s >> t;

    memset(dp, -1, sizeof dp);
    int ans = INF;

    for(int i = 0; i < n; i++)
        if(s[i] == t[0])
            ans = min(ans, solve(i, 1));

    cout << (ans == INF ? -1 : ans) << endl;
}

Compilation message

bajka.cpp: In function 'long long int solve(long long int, long long int)':
bajka.cpp:42:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     if(j == t.size())
      |        ~~^~~~~~~~~~~
bajka.cpp: In function 'void setIO(std::string)':
bajka.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((s+".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   freopen((s+".out").c_str( ),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1004 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 2 ms 1004 KB Output is correct
5 Correct 1 ms 1004 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 12 ms 1004 KB Output is correct
8 Correct 65 ms 1004 KB Output is correct
9 Correct 70 ms 1004 KB Output is correct
10 Correct 1 ms 1004 KB Output is correct
11 Correct 8 ms 1004 KB Output is correct