Submission #499677

#	Time	Username	Problem	Language	Result	Execution time	Memory
499677		keta_tsimakuridze	Boat (APIO16_boat)	C++14	100 / 100	1838 ms	5452 KiB

boat

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 505, mod = 1e9 + 7; // !
int t, L[N], R[N], n, dp[ N][4 *N],fact[N], invfact[N], c[N][N], cc[N], p[N];
vector<int> x;
int pwr(int u,int v) {
            int ans = 1;
            while(v) {
                        if(v % 2) ans = (ll)u * ans % mod;
                        v /= 2; u = (ll)u * u % mod;
            }
            return ans;
}
int C(int a,int b) {
            if(a < b) return 0;
            int x = 1;
            for(int j = a - b + 1; j <= a; j++) x = (ll)x * j % mod;
            return (ll)x * invfact[b] % mod;
}
int C2(int a,int b) {
            if(a < b) return 0;
            return (ll)fact[a] * invfact[a - b] % mod * invfact[b] % mod;
}


void go(int i,int l, int r) {
       for(int j = 0; j <= n; j++) cc[j] = C(r - l + 1, j);
       
       for(int len = 1; len <= n; len++) {
            for(int x = 1; x <= len; x++) c[len][x] = ((ll)cc[x] * C2(len - 1, x - 1) % mod + c[len][x - 1]) % mod;
       }
       for(int j = 1; j <= n; j++) {
            p[j] = p[j - 1];
            if(L[j] <= l && r <= R[j]) p[j]++; 
            if(!(p[j] - p[j - 1])) continue;  
            for(int k = 0; k < j; k++) {
                        dp[j][i] += (ll)dp[k][i - 1] * c[p[j] - p[k]][p[j] - p[k]] % mod;
                        if(dp[j][i] >= mod) dp[j][i] -= mod;
            }
       }
       for(int j = 0; j <= n; j++) {
            dp[j][i] += dp[j][i - 1];
            if(dp[j][i] >= mod) dp[j][i] -= mod;
       }
}
main(){
			ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
            cin >> n;
            fact[0] = invfact[0] = 1;
            for(int i = 1; i <= n; i++) {
                        cin >> L[i] >> R[i];
                        x.push_back(L[i]);
                        x.push_back(R[i] + 1);
                        fact[i] = (ll)fact[i - 1] * i % mod;
                        invfact[i] = (ll)invfact[i - 1] * pwr(i, mod - 2) % mod;
            }
            x.push_back(-1);
            sort(x.begin(), x.end());
            dp[0][0] = 1;

            int cur = 0;
            for(int i = 1; i < x.size(); i++) {
                   if(x[i] < x[i + 1]) go(++cur, x[i], x[i + 1] - 1);
            }
            int ans = 0;
            for(int i = 1; i <= n; i++) {
                        ans = (ans + dp[i][cur]) % mod;
            }
            cout << ans;
}

Compilation message (stderr)

boat.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~
boat.cpp: In function 'int main()':
boat.cpp:66:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i = 1; i < x.size(); i++) {
      |                            ~~^~~~~~~~~~

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