Submission #624384

#	Time	Username	Problem	Language	Result	Execution time	Memory
624384		socpite	Boat (APIO16_boat)	C++14	58 / 100	2081 ms	8416 KiB

boat

#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 505;
const int mod = 1e9+7;

int n;

pair<int, int> A[maxn];
vector<int> cp;

ll dp[maxn][2*maxn], pc[2*maxn][maxn], inv[2*maxn];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    inv[0] = inv[1] = 1;
    for(int i = 2; i < 2*maxn; i++)inv[i]=mod - inv[mod%i]*(mod/i)%mod;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> A[i].f >> A[i].s;
        cp.push_back(A[i].f-1);
        cp.push_back(A[i].s);
    }
    cp.push_back(0);
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for(int i = 1; i < cp.size(); i++){
        ll len = cp[i]-cp[i-1];
        pc[i][1] = len;
        for(int j = 2; j <= n; j++){
            ll crr = len*(len-1)/2;
          	ll sum = 0;
            crr%=mod;
            for(int k = 2; k <= min({n, int(len), j}); k++){
                sum += crr;
                // C(k-2, j-2)*C(k, len)
                if(sum >= mod)sum-=mod;
                crr=crr*(j-k)%mod*inv[k-1]%mod*(len-k)%mod*inv[k+1]%mod;
            }
          	pc[i][j]=sum;
        }
    }
    for(int i = 0; i < cp.size(); i++)dp[0][i]=1;
    for(int i = 0; i <= n; i++)dp[i][0]=1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < cp.size(); j++){
            if(A[i].f > cp[j] || A[i].s <= cp[j-1])dp[i][j]=0;
            else{
                int cnt = 0;
                for(int k = i; k > 0; k--){
                    if(A[k].s >= cp[j] && A[k].f <= cp[j-1]+1){
                        cnt++;
                        dp[i][j]+=dp[k-1][j-1]*pc[j][cnt]%mod;
                        if(dp[i][j] >= mod)dp[i][j]-=mod;
                      	if(dp[i][j] < 0)dp[i][j]+=mod;
                    }
                }
            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
            dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            dp[i][j]%=mod;
        }
    }
    ll ans = dp[n][cp.size()-1]-1;
    ans%=mod;
    if(ans < 0)ans+=mod;
    cout << ans;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = 1; i < cp.size(); i++){
      |                    ~~^~~~~~~~~~~
boat.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < cp.size(); i++)dp[0][i]=1;
      |                    ~~^~~~~~~~~~~
boat.cpp:54:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j = 1; j < cp.size(); j++){
      |                        ~~^~~~~~~~~~~

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