Submission #884889

#	Time	Username	Problem	Language	Result	Execution time	Memory
884889		Ahmed57	Misspelling (JOI22_misspelling)	C++17	28 / 100	93 ms	34604 KiB

misspelling

#include <bits/stdc++.h>
 
using namespace std;
#define int long long
long long dp[201][201][26];
int lol[201][201][2];
long long mod = 1000000007;
vector<int> v[2][201];
int n,m;
long long solve(int i,int j,int la){
    if(i==n+1){
        return 1;
    }
    if(dp[i][j][la]!=-1)return dp[i][j][la];
    long long c1 = 0;
    if(i==1){
        for(int e = 0;e<26;e++){
            c1+=solve(i+1,j,e);
            c1%=mod;
        }
    }else{
        for(int e = 0;e<26;e++){
            if(e==la){
                c1+=solve(i+1,j,e);
            }else{
                if(lol[j][i][0]&&(e>la))continue;
                if(lol[j][i][1]&&(e<la))continue;
                c1+=solve(i+1,i,e);
            }
            c1%=mod;
        }
    }
    return dp[i][j][la] = c1;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        if(a<b){
            v[0][a+1].push_back(b);
        }else{
            v[1][b+1].push_back(a);
        }
    }
    for(int i = 0;i<2;i++){
        for(int j = 1;j<=n;j++){
            sort(v[i][j].begin(),v[i][j].end());
        }
    }
    for(int j = 1;j<n;j++){
        for(int i = j+1;i<=n;i++){
            for(int q = j+1;q<=i;q++){
                int it = lower_bound(v[0][q].begin(),v[0][q].end(),i)-v[0][q].begin();
                if(it!=v[0][q].size()){
                    lol[j][i][0] = 1;
                }
                it = lower_bound(v[1][q].begin(),v[1][q].end(),i)-v[1][q].begin();
                if(it!=v[1][q].size()){
                    lol[j][i][1] = 1;
                }
            }
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<solve(1,1,0)<<endl;
    return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:57:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 if(it!=v[0][q].size()){
      |                    ~~^~~~~~~~~~~~~~~~
misspelling.cpp:61:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 if(it!=v[1][q].size()){
      |                    ~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 0 / 29
• Subtask 4: 0 / 32
• Subtask 5: 0 / 11