oj.uz

Submission #845385

# Submission time Handle Problem Language Result Execution time Memory
845385 2023-09-06T13:25:58 Z vjudge1 Trener (COCI20_trener) C++17
55 / 110
 2000 ms 8584 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

struct node {
    string val;
    vector<int> adj; //asagi
    ll ds = 0;
};

int insides(string s1, string s2) {
    if (s1.find(s2)!=s1.npos) {
        return 1;
    } return 0;
}

int32_t main() {
    int n,k;cin>>n>>k;
    vector<node> nodes(n*k);

    for (int i = 0;i<n;i++) {
        for (int j = 0;j<k;j++) {
            string s1;cin>>s1;nodes[i*k+j].val=s1;
        }
    }
    for (int i = n-1;i>-1;i--){
        for (int j = 0;j<k;j++) {
            if (i==n-1) {nodes[i*k+j].ds=1;continue;}
            nodes[i*k+j].ds=0;
            for (int x = 0;x<k;x++) {
                if (insides(nodes[(i+1)*k+x].val,nodes[i*k+j].val)) {
                    nodes[(i+1)*k+x].adj.push_back(i*k+j);
                    nodes[i*k+j].ds+=nodes[(i+1)*k+x].ds;
                    nodes[i*k+j].ds%=MOD;
                }
            }
        }
    }


    ll t = 0;
    for (int i = 0;i<k;i++){
        t+=nodes[i].ds;
        t%=MOD;
    } cout<<t%MOD<<endl; 

    /* for (int  i = 0;i<n*k;i++) {
        cout<<nodes[i].val<<" "<<nodes[i].ds<<" "<<nodes[i].adj.size()<<endl;
    } */
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 544 KB Output is correct
4 Correct 0 ms 344 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 856 KB Output is correct
2 Correct 26 ms 1036 KB Output is correct
3 Correct 25 ms 856 KB Output is correct
4 Correct 28 ms 3412 KB Output is correct
5 Correct 32 ms 972 KB Output is correct
6 Correct 32 ms 1112 KB Output is correct
7 Correct 28 ms 3416 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 544 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 26 ms 856 KB Output is correct
6 Correct 26 ms 1036 KB Output is correct
7 Correct 25 ms 856 KB Output is correct
8 Correct 28 ms 3412 KB Output is correct
9 Correct 32 ms 972 KB Output is correct
10 Correct 32 ms 1112 KB Output is correct
11 Correct 28 ms 3416 KB Output is correct
12 Execution timed out 2041 ms 8584 KB Time limit exceeded
13 Halted 0 ms 0 KB -