Submission #96115

#TimeUsernameProblemLanguageResultExecution timeMemory
96115oolimryBoat (APIO16_boat)C++14
58 / 100
2055 ms16376 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<long long, long long> ii; long long mod = 1000000007; //long long dp[505][2005]; //static long long dp[505][2005][505]; #define int long long long long modInverse(long long a, long long m) { long long m0 = m; long long y = 0, x = 1; if (m == 1) return 0; while (a > 1) { // q is quotient long long q = a / m; long long t = m; // m is remainder now, process same as // Euclid's algo m = a % m, a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } main() { //freopen("i.txt","r",stdin); ios_base::sync_with_stdio(false); long long inverse[505]; for(long long i = 1;i < 505;i++){ inverse[i] = modInverse(i,mod); } int n; cin >> n; long long a[n]; long long b[n]; set<long long> s; for(int i = 0;i < n;i++){ cin >> a[i] >> b[i]; s.insert(a[i]); s.insert(b[i]); } //cout << s.size() << endl; vector<long long> key; for(set<long long>::iterator it = s.begin();it != s.end();it++){ key.push_back(*it); } //cout << k.size() << endl; vector<ii> ranges; for(int i = 0;i < key.size();i++){ ranges.push_back(ii(key[i],key[i])); if(i != 0){ if(key[i] != key[i-1]+1){ ranges.push_back(ii(key[i-1]+1,key[i]-1)); } } } sort(ranges.begin(),ranges.end()); int m = ranges.size(); //cout << m << "\n"; long long diff[m]; for(int i = 0;i < m;i++){ diff[i] = ranges[i].second - ranges[i].first + 1; diff[i] %= mod; //cout << ranges[i].first << " " << ranges[i].second << "\n"; } long long posa[n]; long long posb[n]; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(ranges[j].first == a[i]) posa[i] = j; if(ranges[j].second == b[i]) posb[i] = j; } } static long long dp[2][2005][505]; //boat no, range, number taken b4; for(int i = 0;i < 2;i++){ for(int j = 0;j < m;j++){ for(int k = 0;k < 505;k++){ dp[i][j][k] = 0ll; } } } for(int j = posa[0];j <= posb[0];j++){ if(a[0] <= ranges[j].first && b[0] >= ranges[j].second){ dp[0][j][1] = diff[j]; //cout << a[0] << " " << ranges[j].first << " " << ranges[j].second << " " << b[0] << endl; } } for(int i = 1;i < n;i++){ ///take nothing for this school int ii = i % 2; for(int j = 0;j < m;j++){ for(int k = 1;k < 505;k++){ if(dp[ii^1][j][k] == 0) break; dp[ii][j][k] = dp[ii^1][j][k]; dp[ii][j][k] %= mod; } } ///take same as previous school for(int j = posa[i];j <= posb[i];j++){ if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){ for(int k = 2;k < 505;k++){ long long x = dp[ii^1][j][k-1]; if(diff[j] - k + 1 <= 0) break; x *= (diff[j] - k + 1); x %= mod; x *= inverse[k]; x %= mod; dp[ii][j][k] += x; //dp[ii][j][k] %= mod; } } } ///take for the first time long long acc = 0ll; for(int j = 0;j < m;j++){ if(j != 0){ for(int k = 1;k < 505;k++){ if(dp[ii^1][j-1][k] == 0) break; acc += dp[ii^1][j-1][k]; acc %= mod; } } if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){ long long x = acc; x += 1; x *= diff[j]; acc %= mod; dp[ii][j][1] += x; dp[ii][j][1] %= mod; } } } /* for(int j = 0;j < m;j++){ cout << ranges[j].first << " " << ranges[j].second << ": "; for(int i = 0;i < n;i++){ cout << dp[i][j] << " "; } cout << "\n"; } */ long long ans = 0ll; for(int j = 0;j < m;j++){ for(int k = 1;k < 505;k++){ ans += dp[(n-1)%2][j][k]; ans %= mod; if(dp[(n-1)%2][j][k] != 0){ //cout << j << " " << k << " " << dp[(n-1)%2][j][k] << "\n"; } } } cout << ans; return 0; }

Compilation message (stderr)

boat.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
boat.cpp: In function 'int main()':
boat.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < key.size();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...