oj.uz

Submission #345633

# Submission time Handle Problem Language Result Execution time Memory
345633 2021-01-07T17:26:41 Z limabeans Trener (COCI20_trener) C++17
55 / 110
 2000 ms 7940 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll mod = 1e9 + 7;



void add(ll &x, ll y) {
    x %= mod;
    x += y;
    x %= mod;
    y %= mod;
}





// s inside t ?
bool inside(string s, string t) {
    return t.find(s) != std::string::npos;
}

int n, k;
string g[55][1505];
ll dp[55][1505];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    for (int i=0; i<n; i++) {
	for (int j=0; j<k; j++) {
	    cin>>g[i][j];
	}
    }

    for (int j=0; j<k; j++) {
	dp[0][j] = 1;
    }

    for (int i=1; i<n; i++) {
	for (int p=0; p<k; p++) {
	    for (int j=0; j<k; j++) {
		if (inside(g[i-1][p], g[i][j])) {
		    add(dp[i][j], dp[i-1][p]);
		}
	    }
	}
    }


    
    ll res = 0;
    for (int j=0; j<k; j++) {
	add(res, dp[n-1][j]);
    }


    cout<<res<<endl;    
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2924 KB Output is correct
2 Correct 2 ms 2924 KB Output is correct
3 Correct 2 ms 2992 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3436 KB Output is correct
2 Correct 39 ms 3436 KB Output is correct
3 Correct 40 ms 3436 KB Output is correct
4 Correct 40 ms 3436 KB Output is correct
5 Correct 53 ms 3436 KB Output is correct
6 Correct 49 ms 3436 KB Output is correct
7 Correct 40 ms 3436 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2924 KB Output is correct
2 Correct 2 ms 2924 KB Output is correct
3 Correct 2 ms 2992 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct
5 Correct 41 ms 3436 KB Output is correct
6 Correct 39 ms 3436 KB Output is correct
7 Correct 40 ms 3436 KB Output is correct
8 Correct 40 ms 3436 KB Output is correct
9 Correct 53 ms 3436 KB Output is correct
10 Correct 49 ms 3436 KB Output is correct
11 Correct 40 ms 3436 KB Output is correct
12 Execution timed out 2083 ms 7940 KB Time limit exceeded
13 Halted 0 ms 0 KB -