제출 #631956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631956		S2speed	Misspelling (JOI22_misspelling)	C++17	28 / 100	21 ms	16340 KiB

misspelling

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 212 , md = 1e9 + 7 , inf = 2e16;

ll a[maxn][2];
vector<ll> b[maxn][2];
ll dp[maxn][maxn][26] , cnt[maxn][2];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	memset(a , -1 , sizeof(a));
	ll n , m;
	cin>>n>>m;
	for(ll i = 0 ; i < m ; i++){
		ll l , r;
		cin>>l>>r; l--; r--;
		bool f = false;
		if(l > r){
			swap(l , r); f = true;
		}
		a[l][f] = max(a[l][f] , r);
	}
	for(ll i = 0 ; i < n ; i++){
		if(a[i][0] != -1){
			b[a[i][0]][0].push_back(i);
		}
		if(a[i][1] != -1){
			b[a[i][1]][1].push_back(i);
		}
	}
	for(ll j = 0 ; j < 26 ; j++){
		dp[0][0][j] = 1;
	}
	for(ll i = 0 ; i < n - 1 ; i++){
		if(a[i][0] != -1){
			for(ll j = 0 ; j <= i ; j++){
				cnt[j][0]++;
			}
		}
		if(a[i][1] != -1){
			for(ll j = 0 ; j <= i ; j++){
				cnt[j][1]++;
			}
		}
		for(ll j = 0 ; j <= i ; j++){
			for(ll k = 0 ; k < 26 ; k++){
				dp[i][j][k] %= md;
			}
		}
		for(ll c = 0 ; c < 2 ; c++){
			for(auto k : b[i][c]){
				for(ll j = 0 ; j <= k ; j++){
					cnt[j][c]--;
				}
			}
		}
		for(ll j = 0 ; j <= i ; j++){
			for(ll k = 0 ; k < 26 ; k++){
				dp[i + 1][j][k] += dp[i][j][k];
				if(cnt[j][0] == 0){
					for(ll t = 0 ; t < k ; t++){
						dp[i + 1][i + 1][t] += dp[i][j][k];
					}
				}
				if(cnt[j][1] == 0){
					for(ll t = k + 1 ; t < 26 ; t++){
						dp[i + 1][i + 1][t] += dp[i][j][k];
					}
				}
			}
		}
	}
	ll ans = 0;
	for(ll j = 0 ; j < n ; j++){
		for(ll k = 0 ; k < 26 ; k++){
			ans += dp[n - 1][j][k];
		}
	}
	ans %= md;
	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