Submission #1023489

#TimeUsernameProblemLanguageResultExecution timeMemory
1023489hackermubBoat (APIO16_boat)C++17
0 / 100
327 ms524288 KiB
#include"bits/stdc++.h" using namespace std; #define int long long #define pii pair<int,int> #define vvi vector<vector<int>> #define sz(v) (int)v.size() #define all(v) v.begin(),v.end() #define bruh cout<<"\nbruh\n"; exit(0); #ifndef debug #define debug(...) #endif const int MOD = 1e9 + 7; int add(int a, int b){ int ans = (a % MOD + b % MOD) % MOD; while(ans < 0) ans += MOD; return ans; } int mul(int a, int b){ int ans = (a % MOD * b % MOD) % MOD; while(ans < 0) ans += MOD; return ans; } // a^-1 = binpow(a, MOD - 2); int binpow(int b, int p){ int ans = 1; b %= MOD; while(p > 0){ if(p & 1) ans = mul(ans, b); b = mul(b, b); p /= 2; } return ans; } int compress(vector<pii>& v){ vector<int> val; for(auto [a, b] : v){ if(!a) continue; val.push_back(a); val.push_back(b); } sort(all(val)); val.erase(unique(all(val))); for(auto& [a, b] : v){ if(!a) continue; a = lower_bound(all(val), a) - val.begin() + 1; b = lower_bound(all(val), b) - val.begin() + 1; } return val.back(); } void solve(){ int n; cin >> n; vector<pii> v(n + 1); for(int i = 1; i <= n; i++){ cin >> v[i].first >> v[i].second; } int MX = compress(v); debug(v, MX); int dp[n + 1][MX + 1]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = v[i].first; j <= v[i].second; j++){ for(int k = 0; k < i; k++){ for(int l = v[k].first; l <= min(j - 1, v[k].second); l++){ dp[i][j] = add(dp[i][j], dp[k][l]); debug(i, j, dp[i][j]); } } } } int ans = 0; for(int i = 1; i <= n; i++){ for(int j = v[i].first; j <= v[i].second; j++){ ans = add(ans, dp[i][j]); } } cout << ans << "\n"; } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(); int T = 1; // cin>>T; for(int ti = 1; ti <= T; ti++){ // cout<< "Case "<<ti<<":\n"; solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...