oj.uz

답안 #530957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530957 2022-02-27T08:10:34 Z Tenis0206 Trener (COCI20_trener) C++11
55 / 110
 2000 ms 8672 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Mod = 1e9 + 7;

const int Mh = 666013;
const int b = 29;

int n,k;
int dp[1505];

string s[1505];

map<int,int> dps,fc;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int j=1; j<=k; j++)
    {
        cin>>s[j];
        int Hash = 0;
        for(auto it : s[j])
        {
            Hash = (1LL * Hash * b + (it - 'a' + 1)) % Mod;
        }
        ++dps[Hash];
    }
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<=k; j++)
        {
            dp[j] = 0;
        }
        for(int j=1; j<=k; j++)
        {
            cin>>s[j];
            fc.clear();
            for(int st=0; st<s[j].size(); st++)
            {
                int Hash = 0;
                for(int dr=st; dr<s[j].size(); dr++)
                {
                    Hash = (1LL * Hash * b + (s[j][dr] - 'a' + 1)) % Mod;
                    if(!fc[Hash])
                    {
                        dp[j] += dps[Hash];
                        dp[j] %= Mod;
                    }
                    ++fc[Hash];
                }
            }
        }
        dps.clear();
        for(int j=1; j<=k; j++)
        {
            int Hash = 0;
            for(auto it : s[j])
            {
                Hash = (1LL * Hash * b + (it - 'a' + 1)) % Mod;
            }
            dps[Hash] += dp[j];
            dps[Hash] %= Mod;
        }
    }
    int rez = 0;
    for(int j=1; j<=k; j++)
    {
        rez += dp[j];
        rez %= Mod;
    }
    cout<<rez<<'\n';
    return 0;
}

Compilation message

trener.cpp: In function 'int main()':
trener.cpp:43:29: 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]
   43 |             for(int st=0; st<s[j].size(); st++)
      |                           ~~^~~~~~~~~~~~
trener.cpp:46:34: 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]
   46 |                 for(int dr=st; dr<s[j].size(); dr++)
      |                                ~~^~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct

Subtask #2
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 826 ms 2236 KB Output is correct
2 Correct 803 ms 1804 KB Output is correct
3 Correct 806 ms 2204 KB Output is correct
4 Correct 41 ms 332 KB Output is correct
5 Correct 647 ms 1344 KB Output is correct
6 Correct 647 ms 1524 KB Output is correct
7 Correct 48 ms 376 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 826 ms 2236 KB Output is correct
6 Correct 803 ms 1804 KB Output is correct
7 Correct 806 ms 2204 KB Output is correct
8 Correct 41 ms 332 KB Output is correct
9 Correct 647 ms 1344 KB Output is correct
10 Correct 647 ms 1524 KB Output is correct
11 Correct 48 ms 376 KB Output is correct
12 Execution timed out 2092 ms 8672 KB Time limit exceeded
13 Halted 0 ms 0 KB -