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
AC × 18
WA × 6
AC × 33
WA × 12
AC × 56
WA × 19
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