Submission #223330

#TimeUsernameProblemLanguageResultExecution timeMemory
223330jamielimTrener (COCI20_trener)C++14
110 / 110
147 ms18400 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD=1000000007; string str[55][1505]; vector<pair<string,int> > str2[55]; int main(){ int n,k; scanf("%d%d",&n,&k); char temp[55]; for(int i=0;i<n;i++){ for(int j=0;j<k;j++){ scanf("%s",temp); str[i][j]=temp; } sort(str[i],str[i]+k); if(i!=0){ for(int j=0;j<k;j++){ string a,b; for(int l=0;l<i;l++){ a+=str[i][j][l]; b+=str[i][j][l+1]; } if(a==b)str2[i].push_back(make_pair(a,j)); else str2[i].push_back(make_pair(a,j)),str2[i].push_back(make_pair(b,j)); } sort(str2[i].begin(),str2[i].end()); //for(int j=0;j<2*k;j++)printf("%s ",str2[i][j].first.c_str()); //printf("\n"); } } ll dp[2][k]; memset(dp,0,sizeof(dp)); for(int i=0;i<k;i++)dp[1][i]=1; for(int i=n-2;i>=0;i--){ int ptr=0; for(int j=0;j<k;j++){ if(j>0&&str[i][j]==str[i][j-1]){ dp[0][j]=dp[0][j-1];continue; } while(ptr<(int)str2[i+1].size()){ if(str[i][j]==str2[i+1][ptr].first){ dp[0][j]+=dp[1][str2[i+1][ptr].second]; dp[0][j]%=MOD; }else if(str[i][j]<str2[i+1][ptr].first)break; ptr++; } } for(int j=0;j<k;j++){dp[1][j]=dp[0][j];dp[0][j]=0;} } ll ans=0; for(int i=0;i<k;i++){ans+=dp[1][i];ans%=MOD;} printf("%lld",ans); }

Compilation message (stderr)

trener.cpp: In function 'int main()':
trener.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
trener.cpp:16:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s",temp);
    ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...