oj.uz

Submission #238558

# Submission time Handle Problem Language Result Execution time Memory
238558 2020-06-11T19:19:23 Z vankata Trener (COCI20_trener) C++14
55 / 110
 2000 ms 1904 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)(1<<11);
const int MOD = (int)(1e9+7);
int n,k;
vector<string>v[2];
long long dp[MAXN][MAXN];
bool cmp(string a,string b)
{
    for(size_t i=0;i<a.size();i++)
    {
        if(a[i]!=b[i])return false;
    }return true;
}
void comp(int t)
{
    int i,j,lm=0,ll=0,l=0;
    string s="";
    for(i=0;i<k;i++)
    {
        for(j=0;j<k;j++)
        {
            lm=ll=0;
            for(l=0;l<v[(t%2)^1][j].size();l++)
            {
                if(v[t%2][i][l]!=v[(t%2)^1][j][l])lm=-1;

                if(v[t%2][i][l+1]!=v[(t%2)^1][j][l])ll=-1;
            }
            if(!lm||!ll)
            {
                dp[t][i]+=dp[t-1][j];
                if(dp[t][i]>=MOD)dp[t][i]-=MOD;
            }
        }
    }
}
void read()
{
    int i,j,t=1;
    string s;
    cin>>n>>k;
    for(i=0;i<k;i++)
    {
        dp[0][i]=1;
        cin>>s;
        v[0].push_back(s);
    }
    for(i=1;i<n;i++)
    {
        v[i%2].clear();
        for(j=0;j<k;j++)
        {
            cin>>s;
            v[i%2].push_back(s);
        }
        comp(i);
    }
    long long ans = 0;
    for(i=0;i<k;i++)
    {
        ans+=dp[n-1][i];
    }
    ans%=MOD;cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    return 0;
}

Compilation message

trener.cpp: In function 'void comp(int)':
trener.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(l=0;l<v[(t%2)^1][j].size();l++)
                     ~^~~~~~~~~~~~~~~~~~~~~
trener.cpp: In function 'void read()':
trener.cpp:40:13: warning: unused variable 't' [-Wunused-variable]
     int i,j,t=1;
             ^

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 768 KB Output is correct
2 Correct 22 ms 768 KB Output is correct
3 Correct 24 ms 768 KB Output is correct
4 Correct 22 ms 768 KB Output is correct
5 Correct 22 ms 768 KB Output is correct
6 Correct 22 ms 768 KB Output is correct
7 Correct 22 ms 768 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 22 ms 768 KB Output is correct
6 Correct 22 ms 768 KB Output is correct
7 Correct 24 ms 768 KB Output is correct
8 Correct 22 ms 768 KB Output is correct
9 Correct 22 ms 768 KB Output is correct
10 Correct 22 ms 768 KB Output is correct
11 Correct 22 ms 768 KB Output is correct
12 Execution timed out 2081 ms 1904 KB Time limit exceeded
13 Halted 0 ms 0 KB -