Submission #667418

#	Time	Username	Problem	Language	Result	Execution time	Memory
667418		MohammadAghil	Boat (APIO16_boat)	C++17	100 / 100	645 ms	4412 KiB

boat

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
 using namespace std;
  typedef long long ll;
   typedef pair<ll, ll> pp;
     #define per(i,r,l) for(int i = (r); i >= (l); i--)
       #define rep(i,l,r) for(int i = (l); i < (r); i++)
          #define all(x) begin(x), end(x)
             #define sz(x) (int)(x).size()
                 #define pb push_back
                     #define ss second
                          #define ff first
                                  void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
     //      freopen("inp.txt", "r", stdin);
     //      freopen("out.txt", "w", stdout);
     // #else
     //      #define er(args ...) 0
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e2 + 5, lg = 17, inf = ll(1e18) + 5, p = 9973;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll,md);return k*k%md*(b&1ll?a:1)%md;}
 
ll dp[maxn][maxn<<1], a[maxn], b[maxn];
ll inv[maxn];

int main(){ IOS();
     inv[0] = 1;
     rep(i,1,maxn) inv[i] = pw(i, mod-2);
     
     int n; cin >> n;
     vector<int> p{0};
     rep(i,1,n+1){
          cin >> a[i] >> b[i];
          b[i]++;
          p.pb(a[i]), p.pb(b[i]);
     }
     sort(all(p)), p.erase(unique(all(p)), end(p));
     int m = sz(p);
     rep(i,0,m) dp[0][i] = 1;
     rep(i,1,n+1){
          int t = upper_bound(all(p), a[i]) - begin(p);
          rep(j,t,m){
               dp[i][j] = dp[i][j-1];
               if(p[j] > b[i]) continue;
               ll cr = p[j] - p[j-1];
               int s = 1;
               per(k,i-1,0){
                    dp[i][j] += cr*dp[k][j-1]%mod;
                    dp[i][j] %= mod;

                    if(a[k] <= p[j-1] && b[k] >= p[j]){
                         cr = cr*(s + p[j] - p[j-1])%mod;
                         s++;
                         cr = cr*inv[s]%mod;
                    }
               }
               // er(i, j, p[j], dp[i][j]);
          }
     } 
     ll ans = 0;
     rep(i,1,n+1) ans += dp[i][m-1], ans %= mod;
     cout << ans << '\n';
     return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42