제출 #631681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631681		alvingogo	Misspelling (JOI22_misspelling)	C++14	100 / 100	1168 ms	282304 KiB

misspelling

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
 
const int mod=1e9+7;
void add(int& x,int y){
    x+=y;
    x-=mod*(x>=mod);
    x+=mod*(x<0);
}
int main(){
    AquA;
    int n;
    cin >> n;
    int m;
    cin >> m;
    vector<vector<int> > dc(n),ic(n),ddc(n+1),dic(n+1);
    vector<int> kd(n,-1),ki(n,-1);
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        if(a<b){
            dc[a+1].push_back(a);
            ddc[b+1].push_back(a);
        }
        else{
            ic[b+1].push_back(b);
            dic[a+1].push_back(b);
        }
    }
    multiset<int> s1,s2;
    for(int i=0;i<n;i++){
        for(auto h:ddc[i]){
            s1.erase(s1.find(h));
        }
        for(auto h:dic[i]){
            s2.erase(s2.find(h));
        }
        for(auto h:dc[i]){
            s1.insert(h);
        }
        for(auto h:ic[i]){
            s2.insert(h);
        }
        if(s1.size()){
            kd[i]=*s1.rbegin();
        }
        if(s2.size()){
            ki[i]=*s2.rbegin();
        }
    }
    vector<vector<int> > dp(n,vector<int>(26));
    vector<vector<int> > pre=dp,pp=dp;
    for(int i=0;i<26;i++){
        dp[0][i]=1;
        pre[0][i]=pre[0][(i>0)*(i-1)]+1;
        pp[0][i]=pre[0][i];
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<26;j++){
            if(j){
                int z=-1;
                if(kd[i]>=0){
                    z=kd[i];
                }
                add(dp[i][j],pp[i-1][j-1]);
                if(z>=0){
                    add(dp[i][j],-pp[z][j-1]);
                }
            }
            int z=-1;
            if(ki[i]>=0){
                z=ki[i];
            }
            add(dp[i][j],pp[i-1][25]);
            add(dp[i][j],-pp[i-1][j]);
            if(z>=0){
                add(dp[i][j],pp[z][j]);
                add(dp[i][j],-pp[z][25]);
            }
            add(pre[i][j],dp[i][j]);
            if(j){
                add(pre[i][j],pre[i][j-1]);
            }
            add(pp[i][j],pp[i-1][j]);
            add(pp[i][j],pre[i][j]);
        }
    }
    cout << pp[n-1][25] << "\n";
    return 0;
}

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