제출 #895317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895317		alexander707070	Misspelling (JOI22_misspelling)	C++14	28 / 100	2828 ms	65212 KiB

misspelling

#include<bits/stdc++.h>
#define MAXN 2007
using namespace std;

const int mod=1e9+7;

int n,m,a,b,ans;

int dp[MAXN][30];
int maxs[MAXN][MAXN],maxs2[MAXN][MAXN],es[MAXN],es2[MAXN];

bool open(int l,int r){
    return maxs[l][r]>=r;
}

bool open2(int l,int r){
    return maxs2[l][r]>=r;
}

void calc_dp(){
    for(int last=0;last<26;last++){
        dp[n][last]=1;
    }

    for(int pos=n-1;pos>=1;pos--){
        for(int last=0;last<26;last++){

            dp[pos][last]=1;
            for(int letter=0;letter<26;letter++){
                for(int nxt=pos+1;nxt<=n;nxt++){
                    if(letter==last)continue;
                    if(letter<last and open(pos+1,nxt))continue;
                    if(letter>last and open2(pos+1,nxt))continue;

                    dp[pos][last]+=dp[nxt][letter];   
                    dp[pos][last]%=mod; 
                }
            }

        }
    }
}


int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a>>b;

        if(a<b){
            es[a+1]=max(es[a+1],b);
        }else{
            es2[b+1]=max(es2[b+1],a);
        }
    }

    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            maxs[i][f]=max(maxs[i][f-1],es[f]);
            maxs2[i][f]=max(maxs2[i][f-1],es2[f]);
        }
    }

    calc_dp();
    for(int i=0;i<26;i++){
        ans+=dp[1][i];
        ans%=mod;
    }

    cout<<ans<<"\n";

    return 0;
}

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