Submission #848667

#TimeUsernameProblemLanguageResultExecution timeMemory
848667danikoynovMisspelling (JOI22_misspelling)C++14
28 / 100
339 ms8700 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const ll mod = 1000000007; const int maxm = 5e5 + 10; const int maxn = 210; int n, m; ll dp[maxn][30]; pair < int, int > con[maxm]; void solve() { cin >> n >> m; for (int i = 1; i <= m; i ++) { cin >> con[i].first >> con[i].second; } for (int j = 0; j < 26; j ++) { dp[1][j] = 1; } for (int i = 1; i <= n - 1; i ++) { int pt_big = n, pt_small = n; for (int d = 1; d <= m; d ++) { if (con[d].first == con[d].second) continue; if (con[d].first < con[d].second) { if (con[d].first >= i + 1 || con[d].second < i + 1) continue; pt_small = min(pt_small, i - con[d].first + 1); /**if (i - j < con[d].first) { small = true; }*/ } else { if (con[d].second >= i + 1 || con[d].first < i + 1) continue; pt_big = min(pt_big, i - con[d].second + 1); /**if (i - j < con[d].second) big = true;*/ } } ///cout << i << " : " << pt_big << " : " << pt_small << endl; for (int j = 1; j <= i; j ++) { if (j < pt_small) { ll sum = 0; for (int c = 0; c < 26; c ++) { dp[i + 1][c] += sum; if (dp[i + 1][c] >= mod) dp[i + 1][c] -= mod; sum += dp[i - j + 1][c]; if (sum >= mod) sum -= mod; } } if (j < pt_big) { ll sum = 0; for (int c = 25; c >= 0; c --) { dp[i + 1][c] += sum; if (dp[i + 1][c] >= mod) dp[i + 1][c] -= mod; sum += dp[i - j + 1][c]; if (sum >= mod) sum -= mod; } } } ///cout << small << " : " << big << endl; } ll ans = 0; for (int i = 1; i <= n; i ++) for (int c = 0; c < 26; c ++) { ans = ans + dp[i][c]; if (ans >= mod) ans -= mod; } cout << ans << endl; } int main() { solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...