Submission #223225

#	Time	Username	Problem	Language	Result	Execution time	Memory
223225		rainy	Trener (COCI20_trener)	C++14	55 / 110	2083 ms	24536 KiB

trener

#include<bits/stdc++.h>
#define INF 2123456789
#define BINF 9123456789123456789
#define pb push_back
#define MAXN 55
#define MAXK 1505
//#define DB
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pl> vpl;
typedef pair<ii,ii>pii;
typedef vector<pii> vpii;
int N,K;
char s[MAXN][MAXK][MAXN];
map<ii,set<ii> >al;
map<ii,int>nw;

int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++){
        for(int j=0;j<K;j++){
            scanf(" %s",&s[i][j]);
            #ifdef DB
            // printf("%d %d: %s\n",i,j,s[i][j]);
            #endif // DB
        }
    }
    for(int i=N-1;i>0;i--){ // highest N row
        for(int j=0;j<K;j++){ // for each surname in high N row
            for(int k=0;k<K;k++){  // for each surname in low N row
                #ifdef DB
                //printf("----\n%s, %s\n",s[i][j],s[i-1][k]);
                #endif // DB
                bool sub=false;
                for(int l=0;l<2;l++){  // for each letter in high N row
                    bool tmp=true;
                    for(int m=0;m<=i-1;m++){ // for each letter in low N row
                        if(s[i][j][l+m]!=s[i-1][k][m]){
                            //printf("%d = %c X %d = %c\n",l,s[i][j][l],m,s[i-1][k][m]);
                            tmp=false;
                            break;
                        }
                        //printf("%d = %c | %d = %c\n",l,s[i][j][l],m,s[i-1][k][m]);
                    }
                    if(tmp){sub=true;break;}
                }
                if(sub){
                    #ifdef DB
                    printf("%s -- %s\n",s[i][j],s[i-1][k]);
                    #endif // DB
                    al[ii(i-1,k)].insert(ii(i,j));
                }
            }
        }
    }
    for(int i=0;i<K;i++)nw[ii(0,i)]=1;
    for(int i=0;i<N-1;i++){ // lower N row
        for(int j=0;j<K;j++){ // lower
            for(int k=0;k<K;k++){ // higher
                if(al[ii(i,j)].count(ii(i+1,k)))
                    nw[ii(i+1,k)]=(nw[ii(i+1,k)]+nw[ii(i,j)])%MOD;
            }
        }
    }
    #ifdef DB
    for(int i=0;i<N;i++){
        for(int j=0;j<K;j++){
            printf("(%d, %d)\t%s\t%d\n",i,j,s[i][j],nw[ii(i,j)]);
        }
    }
    #endif // DB
    int ans=0;
    for(int i=0;i<K;i++){
        ans=(ans+nw[ii(N-1,i)])%MOD;
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

trener.cpp: In function 'int main()':
trener.cpp:28:33: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[55]' [-Wformat=]
             scanf(" %s",&s[i][j]);
                         ~~~~~~~~^
trener.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&K);
     ~~~~~^~~~~~~~~~~~~~
trener.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %s",&s[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55