oj.uz

Submission #238556

# Submission time Handle Problem Language Result Execution time Memory
238556 2020-06-11T19:09:46 Z vankata Trener (COCI20_trener) C++14
55 / 110
 2000 ms 1072 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;
    string s="";
    for(i=0;i<k;i++)
    {
        for(j=0;j<k;j++)
        {
            s=v[(t%2)^1][j];
            s=v[t%2][i][0]+s;
            if(cmp(s,v[t%2][i]))
            {
                dp[t][i]+=dp[t-1][j];
                dp[t][i]%=MOD;

            }
            else
            {
                s=v[(t%2)^1][j] + v[t%2][i][t];
                if(cmp(s,v[t%2][i])){dp[t][i]+=dp[t-1][j];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 read()':
trener.cpp:42: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 5 ms 384 KB Output is correct
2 Correct 5 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 141 ms 888 KB Output is correct
2 Correct 149 ms 1032 KB Output is correct
3 Correct 149 ms 1048 KB Output is correct
4 Correct 80 ms 888 KB Output is correct
5 Correct 157 ms 1072 KB Output is correct
6 Correct 155 ms 888 KB Output is correct
7 Correct 84 ms 888 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 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 141 ms 888 KB Output is correct
6 Correct 149 ms 1032 KB Output is correct
7 Correct 149 ms 1048 KB Output is correct
8 Correct 80 ms 888 KB Output is correct
9 Correct 157 ms 1072 KB Output is correct
10 Correct 155 ms 888 KB Output is correct
11 Correct 84 ms 888 KB Output is correct
12 Execution timed out 2087 ms 1068 KB Time limit exceeded
13 Halted 0 ms 0 KB -