#include <bits/stdc++.h>
using namespace std;
int dp[201][201][26];
int lol[201][201][2];
long long mod = 1000000007;
vector<int> v[2][201];
int n,m;
int 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);
if(c1>=mod)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]&&lol[j][i][1]))continue;
if(lol[j][i][0]&&(e<la))continue;
if(lol[j][i][1]&&(e>la))continue;
c1+=solve(i+1,i,e);
}
if(c1>=mod)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 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
misspelling.cpp: In function 'int main()':
misspelling.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if(it!=v[0][q].size()){
| ~~^~~~~~~~~~~~~~~~
misspelling.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(it!=v[1][q].size()){
| ~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4660 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4572 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4660 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4572 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4568 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Runtime error |
24 ms |
16984 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4660 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4572 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
1 ms |
4660 KB |
Output is correct |
3 |
Incorrect |
1 ms |
4572 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |