Submission #1370771
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(...) _dbg(#__VA_ARGS__",", __VA_ARGS__) void _dbg(string){cout<<endl;} template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);} template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;} template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;} #define INF 1120000000 #define MOD 1000000007 long dp[2][610][610]; long solve(){ int n,m; cin>>n>>m; vector<pair<int,int>> vec(m); rep(i,m) cin>>vec[i].fi>>vec[i].se; vector<int> imos(n+1, 0); rep(i,m)imos[vec[i].fi-1]++, imos[vec[i].se]--; rep(i,n) imos[i+1] += imos[i]; assert(imos[n]==0); rep(i,n) if(imos[i]<2) return 0; vector<int> nums; rep(i,m) nums.pb(vec[i].fi-1), nums.pb(vec[i].fi), nums.pb(vec[i].se); nums.pb(0); uniq(nums); rep(i,m){ vec[i].fi = lower_bound(all(nums), vec[i].fi) - nums.begin(); vec[i].se = lower_bound(all(nums), vec[i].se) - nums.begin(); } sort(all(vec)); //dbg(vec,m); n = nums.size(); auto crnt = dp[0]; auto prev = dp[1]; fill(prev[0], prev[n+1], 0); prev[0][0] = 1; rep(i,m){//dbg(i); for(int j=vec[i].fi-1; j<=vec[i].se; j++){ for(int k=vec[i].fi-1; k<=j; k++) crnt[j][vec[i].se] += prev[k][j]; } for(int j=vec[i].se+1; j<n; j++){ for(int k=vec[i].fi-1; k<=j; k++) crnt[max(vec[i].se,k)][j] += prev[k][j]; } rep(j,n)rep(k,n) crnt[j][k] = (crnt[j][k] + prev[j][k])%MOD; swap(crnt, prev); } return prev[n-1][n-1]; } int main(){ cout << solve() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - ダイヤグラム |
User | tossy |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2077 Byte |
Status | WA |
Exec Time | 181 ms |
Memory | 6016 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 | 2 ms | 2304 KB |
large/case_001.txt | AC | 1 ms | 256 KB |
large/case_002.txt | AC | 2 ms | 2304 KB |
large/case_003.txt | AC | 2 ms | 2304 KB |
large/case_004.txt | AC | 2 ms | 2304 KB |
large/case_005.txt | AC | 2 ms | 2304 KB |
large/case_006.txt | AC | 1 ms | 256 KB |
large/case_007.txt | AC | 1 ms | 256 KB |
large/case_008.txt | AC | 1 ms | 256 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 | WA | 2 ms | 2304 KB |
large/case_013.txt | WA | 2 ms | 2304 KB |
large/case_014.txt | WA | 2 ms | 2304 KB |
large/case_015.txt | WA | 2 ms | 2304 KB |
large/case_016.txt | WA | 2 ms | 2304 KB |
large/case_017.txt | WA | 2 ms | 2304 KB |
large/case_018.txt | WA | 2 ms | 2304 KB |
large/case_019.txt | WA | 2 ms | 2304 KB |
large/case_020.txt | WA | 2 ms | 2304 KB |
large/case_021.txt | WA | 2 ms | 2304 KB |
large/case_022.txt | WA | 2 ms | 2304 KB |
large/case_023.txt | WA | 2 ms | 2304 KB |
large/large_case_000.txt | WA | 181 ms | 6016 KB |
large/large_case_001.txt | WA | 178 ms | 6016 KB |
large/large_case_002.txt | WA | 170 ms | 5888 KB |
large/large_case_003.txt | WA | 175 ms | 5888 KB |
large/large_case_004.txt | WA | 171 ms | 5888 KB |
large/large_case_005.txt | WA | 167 ms | 5888 KB |
large/large_case_006.txt | WA | 176 ms | 6016 KB |
large/large_case_007.txt | WA | 161 ms | 5888 KB |
large/large_case_008.txt | WA | 169 ms | 5888 KB |
large/large_case_009.txt | WA | 179 ms | 6016 KB |
large/large_case_010.txt | WA | 19 ms | 3200 KB |
large/large_case_011.txt | WA | 19 ms | 3200 KB |
large/large_case_012.txt | AC | 1 ms | 256 KB |
large/large_case_013.txt | WA | 17 ms | 3200 KB |
large/large_case_014.txt | WA | 18 ms | 3200 KB |
large/large_case_015.txt | WA | 18 ms | 3200 KB |
large/large_case_016.txt | WA | 19 ms | 3200 KB |
large/large_case_017.txt | WA | 18 ms | 3200 KB |
large/large_case_018.txt | WA | 19 ms | 3200 KB |
large/large_case_019.txt | AC | 1 ms | 256 KB |
large/large_case_020.txt | WA | 177 ms | 6016 KB |
large/large_case_021.txt | WA | 174 ms | 5888 KB |
large/large_case_022.txt | WA | 176 ms | 6016 KB |
large/large_case_023.txt | WA | 171 ms | 6016 KB |
large/large_case_024.txt | WA | 173 ms | 5888 KB |
large/large_case_025.txt | WA | 178 ms | 6016 KB |
large/large_case_026.txt | WA | 177 ms | 6016 KB |
large/large_case_027.txt | WA | 172 ms | 5888 KB |
large/large_case_028.txt | WA | 167 ms | 5888 KB |
large/large_case_029.txt | WA | 180 ms | 6016 KB |
large/medium_case_000.txt | WA | 2 ms | 2432 KB |
large/medium_case_001.txt | WA | 2 ms | 2432 KB |
large/medium_case_002.txt | WA | 2 ms | 2432 KB |
large/medium_case_003.txt | WA | 2 ms | 2432 KB |
large/medium_case_004.txt | WA | 2 ms | 2432 KB |
large/medium_case_005.txt | WA | 2 ms | 2432 KB |
large/medium_case_006.txt | WA | 2 ms | 2432 KB |
large/medium_case_007.txt | WA | 2 ms | 2432 KB |
large/medium_case_008.txt | WA | 2 ms | 2432 KB |
large/medium_case_009.txt | WA | 2 ms | 2432 KB |
large/medium_case_010.txt | WA | 2 ms | 2432 KB |
large/medium_case_011.txt | WA | 2 ms | 2432 KB |
large/medium_case_012.txt | WA | 2 ms | 2432 KB |
large/medium_case_013.txt | WA | 2 ms | 2432 KB |
large/medium_case_014.txt | WA | 2 ms | 2432 KB |
large/medium_case_015.txt | WA | 2 ms | 2304 KB |
large/medium_case_016.txt | WA | 2 ms | 2432 KB |
large/medium_case_017.txt | WA | 2 ms | 2432 KB |
large/medium_case_018.txt | WA | 2 ms | 2432 KB |
large/medium_case_019.txt | WA | 2 ms | 2304 KB |
large/medium_case_020.txt | WA | 2 ms | 2304 KB |
medium/case_000.txt | AC | 2 ms | 2304 KB |
medium/case_001.txt | AC | 1 ms | 256 KB |
medium/case_002.txt | AC | 2 ms | 2304 KB |
medium/case_003.txt | AC | 2 ms | 2304 KB |
medium/case_004.txt | AC | 2 ms | 2304 KB |
medium/case_005.txt | AC | 2 ms | 2304 KB |
medium/case_006.txt | AC | 1 ms | 256 KB |
medium/case_007.txt | AC | 1 ms | 256 KB |
medium/case_008.txt | AC | 1 ms | 256 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 | WA | 2 ms | 2304 KB |
medium/case_013.txt | WA | 2 ms | 2304 KB |
medium/case_014.txt | WA | 2 ms | 2304 KB |
medium/case_015.txt | WA | 2 ms | 2304 KB |
medium/case_016.txt | WA | 2 ms | 2304 KB |
medium/case_017.txt | WA | 2 ms | 2304 KB |
medium/case_018.txt | WA | 2 ms | 2304 KB |
medium/case_019.txt | WA | 2 ms | 2304 KB |
medium/case_020.txt | WA | 2 ms | 2304 KB |
medium/case_021.txt | WA | 2 ms | 2304 KB |
medium/case_022.txt | WA | 2 ms | 2304 KB |
medium/case_023.txt | WA | 2 ms | 2304 KB |
medium/medium_case_000.txt | WA | 2 ms | 2432 KB |
medium/medium_case_001.txt | WA | 2 ms | 2432 KB |
medium/medium_case_002.txt | WA | 2 ms | 2432 KB |
medium/medium_case_003.txt | WA | 2 ms | 2432 KB |
medium/medium_case_004.txt | WA | 2 ms | 2432 KB |
medium/medium_case_005.txt | WA | 2 ms | 2432 KB |
medium/medium_case_006.txt | WA | 2 ms | 2432 KB |
medium/medium_case_007.txt | WA | 2 ms | 2432 KB |
medium/medium_case_008.txt | WA | 2 ms | 2432 KB |
medium/medium_case_009.txt | WA | 2 ms | 2432 KB |
medium/medium_case_010.txt | WA | 2 ms | 2432 KB |
medium/medium_case_011.txt | WA | 2 ms | 2432 KB |
medium/medium_case_012.txt | WA | 2 ms | 2432 KB |
medium/medium_case_013.txt | WA | 2 ms | 2432 KB |
medium/medium_case_014.txt | WA | 2 ms | 2432 KB |
medium/medium_case_015.txt | WA | 2 ms | 2304 KB |
medium/medium_case_016.txt | WA | 2 ms | 2432 KB |
medium/medium_case_017.txt | WA | 2 ms | 2432 KB |
medium/medium_case_018.txt | WA | 2 ms | 2432 KB |
medium/medium_case_019.txt | WA | 2 ms | 2304 KB |
medium/medium_case_020.txt | WA | 2 ms | 2304 KB |
small/case_000.txt | AC | 2 ms | 2304 KB |
small/case_001.txt | AC | 1 ms | 256 KB |
small/case_002.txt | AC | 2 ms | 2304 KB |
small/case_003.txt | AC | 2 ms | 2304 KB |
small/case_004.txt | AC | 2 ms | 2304 KB |
small/case_005.txt | AC | 2 ms | 2304 KB |
small/case_006.txt | AC | 1 ms | 256 KB |
small/case_007.txt | AC | 1 ms | 256 KB |
small/case_008.txt | AC | 1 ms | 256 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 | WA | 2 ms | 2304 KB |
small/case_013.txt | WA | 2 ms | 2304 KB |
small/case_014.txt | WA | 2 ms | 2304 KB |
small/case_015.txt | WA | 2 ms | 2304 KB |
small/case_016.txt | WA | 2 ms | 2304 KB |
small/case_017.txt | WA | 2 ms | 2304 KB |
small/case_018.txt | WA | 2 ms | 2304 KB |
small/case_019.txt | WA | 2 ms | 2304 KB |
small/case_020.txt | WA | 2 ms | 2304 KB |
small/case_021.txt | WA | 2 ms | 2304 KB |
small/case_022.txt | WA | 2 ms | 2304 KB |
small/case_023.txt | WA | 2 ms | 2304 KB |