oj.uz

Submission #845347

# Submission time Handle Problem Language Result Execution time Memory
845347 2023-09-06T13:14:34 Z vjudge1 Trener (COCI20_trener) C++17
110 / 110
 1674 ms 6232 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define int long long
#define pb push_back
#define lim 300000
#define till 40001
// # of primes till 1e6 = 7e4
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
using pii = array<int,2>;

const int mod=1000000007ll;

bool sbc(string*s1,string*s2){
    int i=0;
    bool nope=0;
    for(;i<s1->size();i++){
        if(s1->at(i)!=s2->at(i)){
            nope=1;
            break;
        }
    }
    if(!nope)return 1;
    i=0;
    nope=0;
    for(;i<s1->size();i++){
        if(s1->at(i)!=s2->at(i+1)){
            nope=1;
            break;
        }
    }
    if(!nope)return 1;
    return 0;
}

void solve(){
    int n,k;
    cin>>n>>k;
    string s[n][k];
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cin>>s[i][j];
        }
    }
    int dp[n][k];
    for(int i=0;i<n;i++)for(int j=0;j<k;j++){
        dp[i][j]=0;
    }
    for(int i=0;i<k;i++)dp[n-1][i]=1;
    for(int i=n-2;0<=i;i--){
        for(int j=0;j<k;j++){
            for(int t=0;t<k;t++){
                if(sbc(&s[i][j],&s[i+1][t])){
                    dp[i][j]+=dp[i+1][t];
                    dp[i][j]%=mod;
                }
            }
        }
    }
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++){
            cerr<<dp[i][j]<<" ";
        }cerr<<"\n";
    }
    */
    int ans=0;
    for(int i=0;i<k;i++){
        ans+=dp[0][i];
        ans%=mod;
    }
    cout<<ans<<"\n";
}


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
#ifndef INTERACTIVE
    freopen("in","r",stdin);
#endif
    freopen("out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Compilation message

trener.cpp: In function 'bool sbc(std::string*, std::string*)':
trener.cpp:25:11: 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]
   25 |     for(;i<s1->size();i++){
      |          ~^~~~~~~~~~~
trener.cpp:34:11: 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]
   34 |     for(;i<s1->size();i++){
      |          ~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 816 KB Output is correct
2 Correct 2 ms 828 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 6 ms 604 KB Output is correct
5 Correct 9 ms 828 KB Output is correct
6 Correct 7 ms 604 KB Output is correct
7 Correct 6 ms 604 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 6 ms 604 KB Output is correct
9 Correct 9 ms 828 KB Output is correct
10 Correct 7 ms 604 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 298 ms 6232 KB Output is correct
13 Correct 281 ms 5980 KB Output is correct
14 Correct 281 ms 6084 KB Output is correct
15 Correct 278 ms 6084 KB Output is correct
16 Correct 1314 ms 6188 KB Output is correct
17 Correct 1663 ms 6084 KB Output is correct
18 Correct 1640 ms 6084 KB Output is correct
19 Correct 1651 ms 6088 KB Output is correct
20 Correct 1674 ms 6088 KB Output is correct
21 Correct 1643 ms 6088 KB Output is correct
22 Correct 1286 ms 6088 KB Output is correct