oj.uz

Submission #1001533

# Submission time Handle Problem Language Result Execution time Memory
1001533 2024-06-19T05:31:56 Z vjudge1 Dabbeh (INOI20_dabbeh) C++17
25 / 100
 229 ms 135752 KB 
#include <bits/stdc++.h>
//#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second 
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << endl;\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << (int)x << " ";\
    }\
    cout << endl;\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],d[MAX];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[MAX];
//int e[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int cost[501][501],can[501][501];
void solve(){
    cin >> n >> q;
    for(int i=0;i<n;i++){
        cin >> s[i];
    }
    cin >> s1;
    m=(int)s1.size();
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            k=(int)s[j].size();
            for(z=0;z<k;z++){
                if(s[j][z]!=s1[i+z]){
                    break;
                }
                can[i][i+z]=1;
            }
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cost[i][j]=INF;
        }
    }
    for(int i=0;i<m;i++){
        for(int j=i;j<m;j++){
            if(can[i][j]){
                cost[i][j]=1;
                if(i-1>=0){
                    for(int z=0;z<=i-1;z++){
                        if(cost[z][i-1]!=INF){
                            cost[z][j]=min(cost[z][j],cost[z][i-1]+1);
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<q;i++){
        cin >> x >> y; 
        if(cost[x][y-1]==INF){
            cout << -1 << "\n";
        }
        else{
            cout << cost[x][y-1] << "\n";
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input13.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++; 
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63064 KB Output is correct
2 Correct 60 ms 66648 KB Output is correct
3 Correct 68 ms 67668 KB Output is correct
4 Correct 72 ms 69728 KB Output is correct
5 Correct 78 ms 69996 KB Output is correct
6 Correct 75 ms 70352 KB Output is correct
7 Correct 65 ms 70356 KB Output is correct
8 Correct 85 ms 70328 KB Output is correct
9 Correct 80 ms 70004 KB Output is correct
10 Correct 75 ms 69456 KB Output is correct
11 Correct 87 ms 70020 KB Output is correct
12 Correct 85 ms 69600 KB Output is correct
13 Correct 96 ms 69796 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 229 ms 135752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63064 KB Output is correct
2 Correct 60 ms 66648 KB Output is correct
3 Correct 68 ms 67668 KB Output is correct
4 Correct 72 ms 69728 KB Output is correct
5 Correct 78 ms 69996 KB Output is correct
6 Correct 75 ms 70352 KB Output is correct
7 Correct 65 ms 70356 KB Output is correct
8 Correct 85 ms 70328 KB Output is correct
9 Correct 80 ms 70004 KB Output is correct
10 Correct 75 ms 69456 KB Output is correct
11 Correct 87 ms 70020 KB Output is correct
12 Correct 85 ms 69600 KB Output is correct
13 Correct 96 ms 69796 KB Output is correct
14 Runtime error 229 ms 135752 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -