Submission #1228140
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> P; #define S first #define E second int dp[2][500][500]; int MOD=1000000007LL; signed main(){ int n,m; cin>>n>>m; vector<P> p(m); for(int i=0;i<m;i++) cin>>p[i].S>>p[i].E; sort(p.begin(),p.end()); vector<int> v; for(int i=0;i<m;i++){ v.push_back(p[i].S); v.push_back(p[i].E); } v.push_back(1); v.push_back(n); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); //for(int i=0;i<(int)v.size();i++) cout<<v[i]<<" ";cout<<endl; map<int,int> r; for(int i=0;i<(int)v.size();i++) r[v[i]]=i; dp[0][0][0]=1; for(int i=0;i<m;i++){ bool f=i%2; for(int x=0;x<500;x++) for(int y=0;y<500;y++) dp[!f][x][y]=0; for(int x=0;x<500;x++){ for(int y=x;y<500;y++){ if(!dp[f][x][y]) continue; //cout<<i<<":"<<x<<" "<<y<<" "<<dp[f][x][y]<<endl; //cout<<r[p[i].S]<<" "<<r[p[i].E]<<endl; (dp[!f][x][y]+=dp[f][x][y])%=MOD; if(v[x]+1<p[i].S) continue; int nx=max(x,min(y,r[p[i].E])); int ny=max(y,r[p[i].E]); //cout<<"+"<<nx<<" "<<ny<<endl; (dp[!f][nx][ny]+=dp[f][x][y])%=MOD; } } } cout<<dp[m%2][r[n]][r[n]]<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - ダイヤグラム |
User | beet |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1246 Byte |
Status | WA |
Exec Time | 71 ms |
Memory | 4352 KB |
Judge Result
Set Name | small | medium | large | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 10 | 0 / 40 | 0 / 50 | ||||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
small | small/case_000.txt, small/case_001.txt, small/case_002.txt, small/case_003.txt, small/case_004.txt, small/case_005.txt, small/case_006.txt, small/case_007.txt, small/case_008.txt, small/case_009.txt, small/case_010.txt, small/case_011.txt, small/case_012.txt, small/case_013.txt, small/case_014.txt, small/case_015.txt, small/case_016.txt, small/case_017.txt, small/case_018.txt, small/case_019.txt, small/case_020.txt, small/case_021.txt, small/case_022.txt, small/case_023.txt |
medium | medium/case_000.txt, medium/case_001.txt, medium/case_002.txt, medium/case_003.txt, medium/case_004.txt, medium/case_005.txt, medium/case_006.txt, medium/case_007.txt, medium/case_008.txt, medium/case_009.txt, medium/case_010.txt, medium/case_011.txt, medium/case_012.txt, medium/case_013.txt, medium/case_014.txt, medium/case_015.txt, medium/case_016.txt, medium/case_017.txt, medium/case_018.txt, medium/case_019.txt, medium/case_020.txt, medium/case_021.txt, medium/case_022.txt, medium/case_023.txt, medium/medium_case_000.txt, medium/medium_case_001.txt, medium/medium_case_002.txt, medium/medium_case_003.txt, medium/medium_case_004.txt, medium/medium_case_005.txt, medium/medium_case_006.txt, medium/medium_case_007.txt, medium/medium_case_008.txt, medium/medium_case_009.txt, medium/medium_case_010.txt, medium/medium_case_011.txt, medium/medium_case_012.txt, medium/medium_case_013.txt, medium/medium_case_014.txt, medium/medium_case_015.txt, medium/medium_case_016.txt, medium/medium_case_017.txt, medium/medium_case_018.txt, medium/medium_case_019.txt, medium/medium_case_020.txt |
large | large/case_000.txt, large/case_001.txt, large/case_002.txt, large/case_003.txt, large/case_004.txt, large/case_005.txt, large/case_006.txt, large/case_007.txt, large/case_008.txt, large/case_009.txt, large/case_010.txt, large/case_011.txt, large/case_012.txt, large/case_013.txt, large/case_014.txt, large/case_015.txt, large/case_016.txt, large/case_017.txt, large/case_018.txt, large/case_019.txt, large/case_020.txt, large/case_021.txt, large/case_022.txt, large/case_023.txt, large/large_case_000.txt, large/large_case_001.txt, large/large_case_002.txt, large/large_case_003.txt, large/large_case_004.txt, large/large_case_005.txt, large/large_case_006.txt, large/large_case_007.txt, large/large_case_008.txt, large/large_case_009.txt, large/large_case_010.txt, large/large_case_011.txt, large/large_case_012.txt, large/large_case_013.txt, large/large_case_014.txt, large/large_case_015.txt, large/large_case_016.txt, large/large_case_017.txt, large/large_case_018.txt, large/large_case_019.txt, large/large_case_020.txt, large/large_case_021.txt, large/large_case_022.txt, large/large_case_023.txt, large/large_case_024.txt, large/large_case_025.txt, large/large_case_026.txt, large/large_case_027.txt, large/large_case_028.txt, large/large_case_029.txt, large/medium_case_000.txt, large/medium_case_001.txt, large/medium_case_002.txt, large/medium_case_003.txt, large/medium_case_004.txt, large/medium_case_005.txt, large/medium_case_006.txt, large/medium_case_007.txt, large/medium_case_008.txt, large/medium_case_009.txt, large/medium_case_010.txt, large/medium_case_011.txt, large/medium_case_012.txt, large/medium_case_013.txt, large/medium_case_014.txt, large/medium_case_015.txt, large/medium_case_016.txt, large/medium_case_017.txt, large/medium_case_018.txt, large/medium_case_019.txt, large/medium_case_020.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/case_000.txt | AC | 4 ms | 4096 KB |
large/case_001.txt | AC | 4 ms | 4096 KB |
large/case_002.txt | AC | 4 ms | 4096 KB |
large/case_003.txt | AC | 3 ms | 4096 KB |
large/case_004.txt | AC | 4 ms | 4096 KB |
large/case_005.txt | AC | 4 ms | 4096 KB |
large/case_006.txt | AC | 4 ms | 4096 KB |
large/case_007.txt | AC | 4 ms | 4096 KB |
large/case_008.txt | AC | 4 ms | 4096 KB |
large/case_009.txt | WA | 4 ms | 4096 KB |
large/case_010.txt | WA | 4 ms | 4096 KB |
large/case_011.txt | WA | 4 ms | 4096 KB |
large/case_012.txt | WA | 4 ms | 4096 KB |
large/case_013.txt | WA | 5 ms | 4096 KB |
large/case_014.txt | AC | 5 ms | 4096 KB |
large/case_015.txt | AC | 5 ms | 4096 KB |
large/case_016.txt | AC | 5 ms | 4096 KB |
large/case_017.txt | WA | 5 ms | 4096 KB |
large/case_018.txt | AC | 5 ms | 4096 KB |
large/case_019.txt | AC | 5 ms | 4096 KB |
large/case_020.txt | AC | 5 ms | 4096 KB |
large/case_021.txt | AC | 5 ms | 4096 KB |
large/case_022.txt | AC | 5 ms | 4096 KB |
large/case_023.txt | AC | 5 ms | 4096 KB |
large/large_case_000.txt | AC | 67 ms | 4224 KB |
large/large_case_001.txt | AC | 66 ms | 4224 KB |
large/large_case_002.txt | AC | 64 ms | 4224 KB |
large/large_case_003.txt | AC | 64 ms | 4224 KB |
large/large_case_004.txt | AC | 68 ms | 4224 KB |
large/large_case_005.txt | AC | 71 ms | 4224 KB |
large/large_case_006.txt | AC | 71 ms | 4224 KB |
large/large_case_007.txt | AC | 69 ms | 4352 KB |
large/large_case_008.txt | AC | 65 ms | 4224 KB |
large/large_case_009.txt | AC | 65 ms | 4224 KB |
large/large_case_010.txt | WA | 57 ms | 4224 KB |
large/large_case_011.txt | AC | 47 ms | 4224 KB |
large/large_case_012.txt | AC | 56 ms | 4224 KB |
large/large_case_013.txt | WA | 56 ms | 4224 KB |
large/large_case_014.txt | AC | 53 ms | 4224 KB |
large/large_case_015.txt | WA | 52 ms | 4224 KB |
large/large_case_016.txt | WA | 55 ms | 4224 KB |
large/large_case_017.txt | WA | 56 ms | 4224 KB |
large/large_case_018.txt | WA | 57 ms | 4224 KB |
large/large_case_019.txt | AC | 42 ms | 4224 KB |
large/large_case_020.txt | AC | 66 ms | 4224 KB |
large/large_case_021.txt | AC | 68 ms | 4224 KB |
large/large_case_022.txt | AC | 67 ms | 4224 KB |
large/large_case_023.txt | AC | 70 ms | 4224 KB |
large/large_case_024.txt | AC | 68 ms | 4224 KB |
large/large_case_025.txt | AC | 66 ms | 4224 KB |
large/large_case_026.txt | WA | 66 ms | 4224 KB |
large/large_case_027.txt | AC | 67 ms | 4224 KB |
large/large_case_028.txt | AC | 71 ms | 4224 KB |
large/large_case_029.txt | AC | 66 ms | 4224 KB |
large/medium_case_000.txt | AC | 11 ms | 4096 KB |
large/medium_case_001.txt | AC | 11 ms | 4096 KB |
large/medium_case_002.txt | AC | 11 ms | 4096 KB |
large/medium_case_003.txt | AC | 11 ms | 4096 KB |
large/medium_case_004.txt | WA | 11 ms | 4096 KB |
large/medium_case_005.txt | WA | 11 ms | 4096 KB |
large/medium_case_006.txt | AC | 11 ms | 4096 KB |
large/medium_case_007.txt | AC | 11 ms | 4096 KB |
large/medium_case_008.txt | AC | 11 ms | 4096 KB |
large/medium_case_009.txt | AC | 11 ms | 4096 KB |
large/medium_case_010.txt | AC | 11 ms | 4096 KB |
large/medium_case_011.txt | AC | 11 ms | 4096 KB |
large/medium_case_012.txt | AC | 11 ms | 4096 KB |
large/medium_case_013.txt | AC | 11 ms | 4096 KB |
large/medium_case_014.txt | WA | 11 ms | 4096 KB |
large/medium_case_015.txt | AC | 11 ms | 4096 KB |
large/medium_case_016.txt | WA | 11 ms | 4096 KB |
large/medium_case_017.txt | WA | 11 ms | 4096 KB |
large/medium_case_018.txt | WA | 11 ms | 4096 KB |
large/medium_case_019.txt | AC | 11 ms | 4096 KB |
large/medium_case_020.txt | AC | 11 ms | 4096 KB |
medium/case_000.txt | AC | 4 ms | 4096 KB |
medium/case_001.txt | AC | 4 ms | 4096 KB |
medium/case_002.txt | AC | 4 ms | 4096 KB |
medium/case_003.txt | AC | 3 ms | 4096 KB |
medium/case_004.txt | AC | 4 ms | 4096 KB |
medium/case_005.txt | AC | 4 ms | 4096 KB |
medium/case_006.txt | AC | 4 ms | 4096 KB |
medium/case_007.txt | AC | 4 ms | 4096 KB |
medium/case_008.txt | AC | 4 ms | 4096 KB |
medium/case_009.txt | WA | 4 ms | 4096 KB |
medium/case_010.txt | WA | 4 ms | 4096 KB |
medium/case_011.txt | WA | 4 ms | 4224 KB |
medium/case_012.txt | WA | 4 ms | 4096 KB |
medium/case_013.txt | WA | 5 ms | 4096 KB |
medium/case_014.txt | AC | 5 ms | 4096 KB |
medium/case_015.txt | AC | 5 ms | 4096 KB |
medium/case_016.txt | AC | 5 ms | 4096 KB |
medium/case_017.txt | WA | 5 ms | 4096 KB |
medium/case_018.txt | AC | 5 ms | 4096 KB |
medium/case_019.txt | AC | 5 ms | 4096 KB |
medium/case_020.txt | AC | 5 ms | 4096 KB |
medium/case_021.txt | AC | 5 ms | 4096 KB |
medium/case_022.txt | AC | 5 ms | 4096 KB |
medium/case_023.txt | AC | 5 ms | 4096 KB |
medium/medium_case_000.txt | AC | 11 ms | 4096 KB |
medium/medium_case_001.txt | AC | 11 ms | 4096 KB |
medium/medium_case_002.txt | AC | 11 ms | 4096 KB |
medium/medium_case_003.txt | AC | 11 ms | 4096 KB |
medium/medium_case_004.txt | WA | 11 ms | 4096 KB |
medium/medium_case_005.txt | WA | 11 ms | 4096 KB |
medium/medium_case_006.txt | AC | 11 ms | 4096 KB |
medium/medium_case_007.txt | AC | 11 ms | 4096 KB |
medium/medium_case_008.txt | AC | 11 ms | 4096 KB |
medium/medium_case_009.txt | AC | 11 ms | 4096 KB |
medium/medium_case_010.txt | AC | 11 ms | 4096 KB |
medium/medium_case_011.txt | AC | 11 ms | 4096 KB |
medium/medium_case_012.txt | AC | 11 ms | 4096 KB |
medium/medium_case_013.txt | AC | 11 ms | 4096 KB |
medium/medium_case_014.txt | WA | 11 ms | 4096 KB |
medium/medium_case_015.txt | AC | 11 ms | 4096 KB |
medium/medium_case_016.txt | WA | 11 ms | 4096 KB |
medium/medium_case_017.txt | WA | 11 ms | 4096 KB |
medium/medium_case_018.txt | WA | 11 ms | 4096 KB |
medium/medium_case_019.txt | AC | 11 ms | 4096 KB |
medium/medium_case_020.txt | AC | 11 ms | 4096 KB |
small/case_000.txt | AC | 4 ms | 4096 KB |
small/case_001.txt | AC | 4 ms | 4096 KB |
small/case_002.txt | AC | 4 ms | 4096 KB |
small/case_003.txt | AC | 3 ms | 4096 KB |
small/case_004.txt | AC | 4 ms | 4096 KB |
small/case_005.txt | AC | 4 ms | 4096 KB |
small/case_006.txt | AC | 4 ms | 4096 KB |
small/case_007.txt | AC | 4 ms | 4096 KB |
small/case_008.txt | AC | 4 ms | 4096 KB |
small/case_009.txt | WA | 4 ms | 4096 KB |
small/case_010.txt | WA | 4 ms | 4096 KB |
small/case_011.txt | WA | 4 ms | 4096 KB |
small/case_012.txt | WA | 4 ms | 4096 KB |
small/case_013.txt | WA | 5 ms | 4096 KB |
small/case_014.txt | AC | 5 ms | 4096 KB |
small/case_015.txt | AC | 5 ms | 4096 KB |
small/case_016.txt | AC | 5 ms | 4096 KB |
small/case_017.txt | WA | 5 ms | 4096 KB |
small/case_018.txt | AC | 5 ms | 4096 KB |
small/case_019.txt | AC | 5 ms | 4096 KB |
small/case_020.txt | AC | 5 ms | 4096 KB |
small/case_021.txt | AC | 5 ms | 4096 KB |
small/case_022.txt | AC | 5 ms | 4096 KB |
small/case_023.txt | AC | 5 ms | 4096 KB |