oj.uz

Submission #219369

# Submission time Handle Problem Language Result Execution time Memory
219369 2020-04-05T07:56:12 Z kartel Trener (COCI20_trener) C++14
55 / 110
 2000 ms 104960 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +400500
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

bool go[51][1501][1501];
ll f[51][1501], ans;
int i, j, k, m, p, p1, n;
string s[51][1501];

ll sm(ll x, ll y) {return (x + y) % M;}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
//    in("input.txt");
//    out("output.txt");
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) cin >> s[i][j];
    for (i = 1; i < n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            for (k = 1; k <= m; k++)
            {
                if (s[i + 1][k].find(s[i][j]) != -1) go[i][j][k] = 1;
            }
        }
    }
    for (i = 1; i <= m; i++) f[1][i] = 1;
    for (i = 1; i < n; i++)
        for (j = 1; j <= m; j++)
          for (k = 1; k <= m; k++)
            if (go[i][j][k]) f[i + 1][k] = sm(f[i][j], f[i + 1][k]);

    ans = 0;
    for (i = 1; i <= m; i++) ans = sm(f[n][i], ans);
    cout << ans;
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:50:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (s[i + 1][k].find(s[i][j]) != -1) go[i][j][k] = 1;
                     ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10240 KB Output is correct
2 Correct 20 ms 10112 KB Output is correct
3 Correct 20 ms 10112 KB Output is correct
4 Correct 18 ms 10624 KB Output is correct
5 Correct 29 ms 10488 KB Output is correct
6 Correct 29 ms 10488 KB Output is correct
7 Correct 19 ms 10752 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 6 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 20 ms 10240 KB Output is correct
6 Correct 20 ms 10112 KB Output is correct
7 Correct 20 ms 10112 KB Output is correct
8 Correct 18 ms 10624 KB Output is correct
9 Correct 29 ms 10488 KB Output is correct
10 Correct 29 ms 10488 KB Output is correct
11 Correct 19 ms 10752 KB Output is correct
12 Execution timed out 2090 ms 104960 KB Time limit exceeded
13 Halted 0 ms 0 KB -