제출 #550397

#제출 시각아이디문제언어결과실행 시간메모리
550397farhan132Boat (APIO16_boat)C++17
100 / 100
1588 ms8500 KiB
/***Farhan132***/ //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") //#pragma GCC optimization ("unroll-loops") //#pragma GCC optimize("Ofast,fast-math") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef double dd; typedef vector<ll> vll; typedef pair<ll , ll> ii; typedef vector< ii > vii; typedef pair < pair < ll , ll > , pair < ll , ll > > cm; typedef tuple < ll, ll, ll > tp; #define ff first #define ss second #define pb push_back #define in insert #define f0(b) for(int i=0;i<(b);i++) #define f00(b) for(int j=0;j<(b);j++) #define f1(b) for(int i=1;i<=(b);i++) #define f11(b) for(int j=1;j<=(b);j++) #define f2(a,b) for(int i=(a);i<=(b);i++) #define f22(a,b) for(int j=(a);j<=(b);j++) #define sf(a) scanf("%lld",&a) #define sff(a,b) scanf("%lld %lld", &a , &b) #define pf(a) printf("%lld\n",a) #define pff(a,b) printf("%lld %lld\n", a , b) #define bug printf("**!\n") #define mem(a , b) memset(a, b ,sizeof(a)) #define front_zero(n) __builtin_clzll(n) #define back_zero(n) __builtin_ctzll(n) #define total_one(n) __builtin_popcount(n) #define clean fflush(stdout) //const ll mod = (ll) 998244353; const ll mod = (ll) 1e9 + 7; const ll maxn = (ll)1e8 + 5; const int nnn = 1048590; const int inf = numeric_limits<int>::max()-1; //const ll INF = numeric_limits<ll>::max()-1; const ll INF = (ll)1e18; ll dx[]={0,1,0,-1}; ll dy[]={1,0,-1,0}; ll dxx[]={0,1,0,-1,1,1,-1,-1}; ll dyy[]={1,0,-1,0,1,-1,1,-1}; bool USACO = 0; mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll N = 505; ll fac[N], inv[N], num[N]; ll pw(ll a , ll b){ ll res = 1; while(b){ if(b&1) res = (res*a)%mod; a = (a*a)%mod; b /= 2; } return res; } void pre(ll n){ fac[0] = 1; inv[0] = pw(fac[0], mod - 2); for(ll i = 1; i < n; i++){ fac[i] = (fac[i-1] * i)%mod; inv[i] = pw(fac[i], mod - 2); num[i] = pw(i, mod - 2); } return; } ll nCr(ll n , ll r){ if(n == r) return 1; if(n < r) return 0; ll ans = fac[n] * (inv[r]); ans %= mod; ans *= inv[n - r]; return ans%mod; } ll dp[N][2*N]; ll combo[2*N][N]; ll a[N] , b[N]; void solve(){ ll n; cin >> n; vector < ll > idx; idx.pb(0); idx.pb(1); for(ll i = 1; i <= n; i++){ cin >> a[i] >> b[i]; idx.pb(a[i]); idx.pb(b[i] + 1); } sort(idx.begin(), idx.end()); idx.erase(unique(idx.begin(), idx.end()), idx.end()); mem(dp, 0); ll sz = idx.size(); for(ll i = 0; i < sz - 1; i++){ ll len = idx[i + 1] - idx[i]; for(ll j = 0; j <= n; j++){ combo[i][j] = 0; ll res = 1, l = len; for(ll x = 1; x <= j; x++){ res = (res * l)%mod; l--; res = (res * num[x])%mod; combo[i][j] += nCr(j - 1, x - 1) * res; combo[i][j] %= mod; } } } for(ll i = 0; i < sz; i++) dp[0][i] = 1; ll ans = 0; for(ll i = 1; i <= n; i++){ a[i] = lower_bound(idx.begin(), idx.end(), a[i]) - idx.begin(); b[i] = upper_bound(idx.begin(), idx.end(), b[i]) - idx.begin() - 1; dp[i][0] = 0; for(ll x = a[i]; x <= b[i]; x++){ ll cnt = 1; ll len = idx[x + 1] - idx[x]; for(ll j = i - 1; j >= 0; j--){ dp[i][x] += combo[x][cnt] * dp[j][x - 1]; dp[i][x] %= mod; if(a[j] <= x && b[j] >= x) cnt++; } } for(ll x = 1; x < sz; x++) dp[i][x] = (dp[i][x - 1] + dp[i][x])%mod; ans += dp[i][sz-1]; } cout << ans%mod << '\n'; return; } int main() { #ifdef LOCAL freopen("in", "r", stdin); freopen("out", "w", stdout); auto start_time = clock(); #else ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); #endif pre(N); ll T = 1, CT = 0; //cin >> T; while(T--){ // cout << "Case #" << ++CT <<": " ; solve(); } #ifdef LOCAL auto end_time = clock(); cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n"; #endif return 0; }

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'void solve()':
boat.cpp:143:12: warning: unused variable 'len' [-Wunused-variable]
  143 |         ll len = idx[x + 1] - idx[x];
      |            ^~~
boat.cpp: In function 'int main()':
boat.cpp:172:15: warning: unused variable 'CT' [-Wunused-variable]
  172 |     ll T = 1, CT = 0;  //cin >> T;
      |               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...