Submission #970700

#TimeUsernameProblemLanguageResultExecution timeMemory
970700VinhLuuBoat (APIO16_boat)C++17
9 / 100
237 ms8536 KiB
//#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(lmao) lmao.begin(), lmao.end() using namespace std; typedef pair<int,int> pii; typedef tuple<int,int,int> tp; const int N = 1005; int block = 555; const int mod = 1e9 + 7; //const ll oo = 5e18; int n, L[N], R[N]; ll f[N][N], inv[N]; ll lt(ll u,ll v){ if(v == 0) return 1; ll x = u, kq = 1; while(v){ if(v & 1) kq = kq * x % mod; x = x * x % mod; v /= 2; } return kq; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "v" if(fopen(task ".inp","r")){ freopen(task ".inp","r",stdin); freopen(task ".out","w",stdout); } cin >> n; vector<int> rrh; for(int i = 1; i <= n; i ++){ cin >> L[i] >> R[i]; rrh.pb(L[i]); rrh.pb(R[i] + 1); } sort(all(rrh)); rrh.resize(unique(all(rrh)) - rrh.begin()); // for(auto j : rrh) cerr << j << " t\n"; inv[0] = f[0][0] = 1; for(int i = 1; i <= n + 1; i ++) inv[i] = lt(i, mod - 2); for(int i = 1; i < rrh.size(); i ++){ // cerr << i << " h\n"; f[i][0] = 1; for(int j = 1; j <= n; j ++) if(L[j] <= rrh[i - 1] && rrh[i - 1] <= R[j]){ f[i][j] = f[i - 1][j]; ll w = rrh[i] - rrh[i - 1], pick = 1; for(int k = 1; k <= j; k ++){ if(L[j - k + 1] <= rrh[i - 1] && rrh[i - 1] <= R[j - k + 1]){ if(k <= w) pick = pick * (w - k + 1) % mod * inv[k] % mod; f[i][j] = (f[i][j] + f[i - 1][j - k] * pick % mod) % mod; }else f[i][j] = (f[i][j] + f[i - 1][j - k] * pick % mod) % mod; } // cerr << i << " " << j << " " << f[i][j] << " k\n"; }else{ f[i][j] = f[i - 1][j]; // cerr << i << " " << j << " " << f[i][j] << " k\n"; } } ll ans = 0; for(int i = 1; i <= n; i ++) ans = (ans + f[rrh.size() - 1][i]) % mod; cout << ans; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:56:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i = 1; i < rrh.size(); i ++){
      |                    ~~^~~~~~~~~~~~
boat.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...