Submission #480664

#TimeUsernameProblemLanguageResultExecution timeMemory
480664TAMREFBoat (APIO16_boat)C++17
100 / 100
1427 ms8352 KiB
#include <bits/stdc++.h> #define va first #define vb second #define lb lower_bound #define ub upper_bound #define bs binary_search #define pp push_back #define ep emplace_back #define all(v) (v).begin(),(v).end() #define szz(v) ((int)(v).size()) #define bi_pc __builtin_popcount #define bi_pcll __builtin_popcountll #define bi_tz __builtin_ctz #define bi_tzll __builtin_ctzll #define fio ios_base::sync_with_stdio(0);cin.tie(0); #ifdef TAMREF #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) 42 #endif using namespace std; using ll = long long; using lf = long double; using pii = pair<int,int>; using ppi = pair<int,pii>; using pll = pair<ll,ll>; using pff = pair<lf,lf>; using ti = tuple<int,int,int>; using base = complex<double>; const lf PI = 3.14159265358979323846264338L; template <typename T> inline T umax(T& u, T v){return u = max(u, v);} template <typename T> inline T umin(T& u, T v){return u = min(u, v);} mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mod = 1e9 + 7; ll inv[505] = {0, 1}; int n; vector<int> cmp; int a[505], b[505]; ll a_Ijk[2][1005][505]; // i' < i, j' = j, k' = k ll b_ij[2][1005]; //i' < i, j' < j, k' arb ll ans; int main(){ fio; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; ++b[i]; cmp.pp(a[i]); cmp.pp(b[i]); } for(int i = 2; i <= n; i++) { inv[i] = mod - inv[mod % i] * (mod / i) % mod; debug("inv[%d] = %lld\n", i, inv[i]); } sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end()); int d = szz(cmp); for(int i = 1; i <= n; i++) { a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1; b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1; } for(int i = 1; i <= n; i++) { for(int j = 1; j < d; j++) { b_ij[i & 1][j] = (b_ij[~i & 1][j] + b_ij[i & 1][j-1] + mod - b_ij[~i & 1][j-1]) % mod; for(int k = 1; k <= n; k++) { a_Ijk[i & 1][j][k] = a_Ijk[~i & 1][j][k]; ll dp = 0; if(a[i] <= j && j < b[i]) { ll len = cmp[j] - cmp[j-1]; if(k == 1) { dp = (1 + b_ij[~i & 1][j-1]) * len % mod; }else{ dp = a_Ijk[~i & 1][j][k-1] * (len - k + 1) % mod * inv[k] % mod; } } (a_Ijk[i & 1][j][k] += dp) %= mod; b_ij[i & 1][j] += dp; ans += dp; } b_ij[i & 1][j] %= mod; } } cout << ans % mod << endl; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:56:9: note: in expansion of macro 'debug'
   56 |         debug("inv[%d] = %lld\n", i, inv[i]);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...