Submission #2932067
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cstdio> #include <cstring> #include <math.h> using namespace std; typedef long long ll; typedef double D; typedef pair<int,int> P; #define M 1000000007 #define F first #define S second #define PB push_back int n,m,k; int dp[205][405][405]; vector<int>cm; map<int,int>p; P a[205]; int main(void){ cin>>n>>m; for(int i=0;i<m;i++){ int x,y; cin>>x>>y; cm.PB(x); cm.PB(y); a[i]=P(x,y); } sort(cm.begin(),cm.end()); cm.erase(unique(cm.begin(),cm.end()),cm.end()); k=cm.size(); for(int i=0;i<k-1;i++){ if(cm[i]+1<cm[i+1])cm.PB(cm[i]+1); } cm.PB(1); cm.PB(n); sort(cm.begin(),cm.end()); cm.erase(unique(cm.begin(),cm.end()),cm.end()); k=cm.size(); for(int i=0;i<k;i++)p[cm[i]]=i; for(int i=0;i<m;i++){ a[i].F=p[a[i].F]; a[i].S=p[a[i].S]; } sort(a,a+m); dp[0][0][0]=1; for(int i=0;i<m;i++){ for(int j=0;j<=k;j++){ for(int l=j;l<=k;l++){ int x=max(j,min(l,a[i].S+1)),y=max(l,a[i].S+1); if(a[i].F<=j)dp[i+1][x][y]=(dp[i+1][x][y]+dp[i][j][l])%M; dp[i+1][j][l]=(dp[i+1][j][l]+dp[i][j][l])%M; } } } cout<<dp[m][k][k]<<endl; }
Submission Info
Submission Time | |
---|---|
Task | H - ダイヤグラム |
User | nxteru |
Language | C++14 (GCC 5.4.1) |
Score | 50 |
Code Size | 1443 Byte |
Status | WA |
Exec Time | 284 ms |
Memory | 130688 KB |
Judge Result
Set Name | small | medium | large | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 10 / 10 | 40 / 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 | 1 ms | 256 KB |
large/case_001.txt | AC | 2 ms | 2304 KB |
large/case_002.txt | AC | 2 ms | 2304 KB |
large/case_003.txt | AC | 1 ms | 256 KB |
large/case_004.txt | AC | 1 ms | 256 KB |
large/case_005.txt | AC | 2 ms | 2304 KB |
large/case_006.txt | AC | 2 ms | 2304 KB |
large/case_007.txt | AC | 2 ms | 4352 KB |
large/case_008.txt | AC | 2 ms | 2304 KB |
large/case_009.txt | AC | 2 ms | 2304 KB |
large/case_010.txt | AC | 2 ms | 2304 KB |
large/case_011.txt | AC | 2 ms | 2304 KB |
large/case_012.txt | AC | 2 ms | 4352 KB |
large/case_013.txt | AC | 2 ms | 4352 KB |
large/case_014.txt | AC | 2 ms | 4352 KB |
large/case_015.txt | AC | 2 ms | 4352 KB |
large/case_016.txt | AC | 2 ms | 4352 KB |
large/case_017.txt | AC | 2 ms | 4352 KB |
large/case_018.txt | AC | 2 ms | 4352 KB |
large/case_019.txt | AC | 2 ms | 4352 KB |
large/case_020.txt | AC | 2 ms | 4352 KB |
large/case_021.txt | AC | 2 ms | 4352 KB |
large/case_022.txt | AC | 2 ms | 4352 KB |
large/case_023.txt | AC | 2 ms | 4352 KB |
large/large_case_000.txt | WA | 284 ms | 130688 KB |
large/large_case_001.txt | WA | 278 ms | 130688 KB |
large/large_case_002.txt | WA | 267 ms | 130688 KB |
large/large_case_003.txt | WA | 269 ms | 130688 KB |
large/large_case_004.txt | WA | 271 ms | 130688 KB |
large/large_case_005.txt | WA | 271 ms | 130688 KB |
large/large_case_006.txt | WA | 282 ms | 130688 KB |
large/large_case_007.txt | WA | 265 ms | 130688 KB |
large/large_case_008.txt | WA | 263 ms | 130688 KB |
large/large_case_009.txt | WA | 275 ms | 130688 KB |
large/large_case_010.txt | AC | 44 ms | 128000 KB |
large/large_case_011.txt | AC | 44 ms | 128000 KB |
large/large_case_012.txt | AC | 44 ms | 128000 KB |
large/large_case_013.txt | AC | 44 ms | 128000 KB |
large/large_case_014.txt | AC | 44 ms | 128000 KB |
large/large_case_015.txt | AC | 43 ms | 128000 KB |
large/large_case_016.txt | AC | 44 ms | 128000 KB |
large/large_case_017.txt | AC | 44 ms | 128000 KB |
large/large_case_018.txt | AC | 43 ms | 128000 KB |
large/large_case_019.txt | AC | 43 ms | 128000 KB |
large/large_case_020.txt | WA | 274 ms | 130688 KB |
large/large_case_021.txt | WA | 275 ms | 130688 KB |
large/large_case_022.txt | WA | 276 ms | 130688 KB |
large/large_case_023.txt | WA | 273 ms | 130688 KB |
large/large_case_024.txt | WA | 270 ms | 130688 KB |
large/large_case_025.txt | WA | 279 ms | 130688 KB |
large/large_case_026.txt | WA | 275 ms | 130688 KB |
large/large_case_027.txt | WA | 272 ms | 130688 KB |
large/large_case_028.txt | WA | 272 ms | 130688 KB |
large/large_case_029.txt | WA | 274 ms | 130688 KB |
large/medium_case_000.txt | AC | 6 ms | 24960 KB |
large/medium_case_001.txt | AC | 6 ms | 25088 KB |
large/medium_case_002.txt | AC | 6 ms | 24960 KB |
large/medium_case_003.txt | AC | 6 ms | 24960 KB |
large/medium_case_004.txt | AC | 6 ms | 25088 KB |
large/medium_case_005.txt | AC | 6 ms | 24960 KB |
large/medium_case_006.txt | AC | 6 ms | 24960 KB |
large/medium_case_007.txt | AC | 6 ms | 25088 KB |
large/medium_case_008.txt | AC | 6 ms | 24960 KB |
large/medium_case_009.txt | AC | 6 ms | 24960 KB |
large/medium_case_010.txt | AC | 6 ms | 24960 KB |
large/medium_case_011.txt | AC | 6 ms | 24960 KB |
large/medium_case_012.txt | AC | 6 ms | 24960 KB |
large/medium_case_013.txt | AC | 6 ms | 24960 KB |
large/medium_case_014.txt | AC | 6 ms | 24960 KB |
large/medium_case_015.txt | AC | 6 ms | 24960 KB |
large/medium_case_016.txt | AC | 6 ms | 24960 KB |
large/medium_case_017.txt | AC | 6 ms | 24960 KB |
large/medium_case_018.txt | AC | 6 ms | 24960 KB |
large/medium_case_019.txt | AC | 6 ms | 24960 KB |
large/medium_case_020.txt | AC | 6 ms | 24832 KB |
medium/case_000.txt | AC | 1 ms | 256 KB |
medium/case_001.txt | AC | 2 ms | 2304 KB |
medium/case_002.txt | AC | 1 ms | 2304 KB |
medium/case_003.txt | AC | 1 ms | 256 KB |
medium/case_004.txt | AC | 1 ms | 256 KB |
medium/case_005.txt | AC | 2 ms | 2304 KB |
medium/case_006.txt | AC | 1 ms | 2304 KB |
medium/case_007.txt | AC | 2 ms | 4352 KB |
medium/case_008.txt | AC | 1 ms | 2304 KB |
medium/case_009.txt | AC | 2 ms | 2304 KB |
medium/case_010.txt | AC | 2 ms | 2304 KB |
medium/case_011.txt | AC | 2 ms | 2304 KB |
medium/case_012.txt | AC | 2 ms | 4352 KB |
medium/case_013.txt | AC | 2 ms | 4352 KB |
medium/case_014.txt | AC | 2 ms | 4352 KB |
medium/case_015.txt | AC | 2 ms | 4352 KB |
medium/case_016.txt | AC | 2 ms | 4352 KB |
medium/case_017.txt | AC | 2 ms | 4352 KB |
medium/case_018.txt | AC | 2 ms | 4352 KB |
medium/case_019.txt | AC | 2 ms | 4352 KB |
medium/case_020.txt | AC | 2 ms | 4352 KB |
medium/case_021.txt | AC | 2 ms | 4352 KB |
medium/case_022.txt | AC | 2 ms | 4352 KB |
medium/case_023.txt | AC | 2 ms | 4352 KB |
medium/medium_case_000.txt | AC | 6 ms | 24960 KB |
medium/medium_case_001.txt | AC | 6 ms | 25088 KB |
medium/medium_case_002.txt | AC | 6 ms | 24960 KB |
medium/medium_case_003.txt | AC | 6 ms | 24960 KB |
medium/medium_case_004.txt | AC | 6 ms | 25088 KB |
medium/medium_case_005.txt | AC | 6 ms | 24960 KB |
medium/medium_case_006.txt | AC | 6 ms | 24960 KB |
medium/medium_case_007.txt | AC | 6 ms | 25088 KB |
medium/medium_case_008.txt | AC | 6 ms | 24960 KB |
medium/medium_case_009.txt | AC | 6 ms | 24960 KB |
medium/medium_case_010.txt | AC | 6 ms | 24960 KB |
medium/medium_case_011.txt | AC | 6 ms | 24960 KB |
medium/medium_case_012.txt | AC | 6 ms | 24960 KB |
medium/medium_case_013.txt | AC | 6 ms | 24960 KB |
medium/medium_case_014.txt | AC | 6 ms | 24960 KB |
medium/medium_case_015.txt | AC | 6 ms | 24960 KB |
medium/medium_case_016.txt | AC | 6 ms | 24960 KB |
medium/medium_case_017.txt | AC | 6 ms | 24960 KB |
medium/medium_case_018.txt | AC | 6 ms | 24960 KB |
medium/medium_case_019.txt | AC | 6 ms | 24960 KB |
medium/medium_case_020.txt | AC | 6 ms | 24832 KB |
small/case_000.txt | AC | 1 ms | 256 KB |
small/case_001.txt | AC | 2 ms | 2304 KB |
small/case_002.txt | AC | 2 ms | 2304 KB |
small/case_003.txt | AC | 1 ms | 256 KB |
small/case_004.txt | AC | 1 ms | 256 KB |
small/case_005.txt | AC | 2 ms | 2304 KB |
small/case_006.txt | AC | 2 ms | 2304 KB |
small/case_007.txt | AC | 2 ms | 4352 KB |
small/case_008.txt | AC | 2 ms | 2304 KB |
small/case_009.txt | AC | 2 ms | 2304 KB |
small/case_010.txt | AC | 2 ms | 2304 KB |
small/case_011.txt | AC | 2 ms | 2304 KB |
small/case_012.txt | AC | 2 ms | 4352 KB |
small/case_013.txt | AC | 2 ms | 4352 KB |
small/case_014.txt | AC | 2 ms | 4352 KB |
small/case_015.txt | AC | 2 ms | 4352 KB |
small/case_016.txt | AC | 3 ms | 4352 KB |
small/case_017.txt | AC | 2 ms | 4352 KB |
small/case_018.txt | AC | 2 ms | 4352 KB |
small/case_019.txt | AC | 2 ms | 4352 KB |
small/case_020.txt | AC | 2 ms | 4352 KB |
small/case_021.txt | AC | 2 ms | 4352 KB |
small/case_022.txt | AC | 2 ms | 4352 KB |
small/case_023.txt | AC | 2 ms | 4352 KB |