oj.uz

Submission #624365

# Submission time Handle Problem Language Result Execution time Memory
624365 2022-08-08T04:09:07 Z socpite Boat (APIO16_boat) C++14
9 / 100
 1133 ms 12444 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

typedef long long ll;

const int maxn = 1005;
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[maxn];


int main(){
    inv[0] = inv[1] = 1;
    for(int i = 2; i < 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;
            crr%=mod;
            for(int k = 2; k <= min({n, int(len), j}); k++){
                pc[i][j] += crr;
                // C(k-2, j)*C(k, len)
                if(pc[i][j] >= mod)pc[i][j]-=mod;
                k-=2;
                crr=crr*(j-k)%mod;
                crr=crr*inv[k+1]%mod;
                k+=2;
                crr=crr*(len-k)%mod;
                crr=crr*inv[k+1]%mod;
            }
        }
    }
    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;
                        dp[i][j]%=mod;
                    }
                }
            }
            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

boat.cpp: In function 'int main()':
boat.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 12168 KB Output is correct
2 Correct 1127 ms 12196 KB Output is correct
3 Correct 1132 ms 12128 KB Output is correct
4 Correct 1131 ms 12360 KB Output is correct
5 Correct 1130 ms 12168 KB Output is correct
6 Correct 1131 ms 12444 KB Output is correct
7 Correct 1129 ms 12168 KB Output is correct
8 Correct 1133 ms 12308 KB Output is correct
9 Correct 1133 ms 12116 KB Output is correct
10 Correct 1133 ms 12236 KB Output is correct
11 Correct 1130 ms 12188 KB Output is correct
12 Correct 1128 ms 12228 KB Output is correct
13 Correct 1129 ms 12220 KB Output is correct
14 Correct 1133 ms 12248 KB Output is correct
15 Correct 1133 ms 12152 KB Output is correct
16 Correct 204 ms 4008 KB Output is correct
17 Correct 216 ms 4176 KB Output is correct
18 Correct 210 ms 4076 KB Output is correct
19 Correct 218 ms 4292 KB Output is correct
20 Correct 209 ms 4080 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 12168 KB Output is correct
2 Correct 1127 ms 12196 KB Output is correct
3 Correct 1132 ms 12128 KB Output is correct
4 Correct 1131 ms 12360 KB Output is correct
5 Correct 1130 ms 12168 KB Output is correct
6 Correct 1131 ms 12444 KB Output is correct
7 Correct 1129 ms 12168 KB Output is correct
8 Correct 1133 ms 12308 KB Output is correct
9 Correct 1133 ms 12116 KB Output is correct
10 Correct 1133 ms 12236 KB Output is correct
11 Correct 1130 ms 12188 KB Output is correct
12 Correct 1128 ms 12228 KB Output is correct
13 Correct 1129 ms 12220 KB Output is correct
14 Correct 1133 ms 12248 KB Output is correct
15 Correct 1133 ms 12152 KB Output is correct
16 Correct 204 ms 4008 KB Output is correct
17 Correct 216 ms 4176 KB Output is correct
18 Correct 210 ms 4076 KB Output is correct
19 Correct 218 ms 4292 KB Output is correct
20 Correct 209 ms 4080 KB Output is correct
21 Incorrect 155 ms 12432 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1121 ms 12168 KB Output is correct
2 Correct 1127 ms 12196 KB Output is correct
3 Correct 1132 ms 12128 KB Output is correct
4 Correct 1131 ms 12360 KB Output is correct
5 Correct 1130 ms 12168 KB Output is correct
6 Correct 1131 ms 12444 KB Output is correct
7 Correct 1129 ms 12168 KB Output is correct
8 Correct 1133 ms 12308 KB Output is correct
9 Correct 1133 ms 12116 KB Output is correct
10 Correct 1133 ms 12236 KB Output is correct
11 Correct 1130 ms 12188 KB Output is correct
12 Correct 1128 ms 12228 KB Output is correct
13 Correct 1129 ms 12220 KB Output is correct
14 Correct 1133 ms 12248 KB Output is correct
15 Correct 1133 ms 12152 KB Output is correct
16 Correct 204 ms 4008 KB Output is correct
17 Correct 216 ms 4176 KB Output is correct
18 Correct 210 ms 4076 KB Output is correct
19 Correct 218 ms 4292 KB Output is correct
20 Correct 209 ms 4080 KB Output is correct
21 Incorrect 155 ms 12432 KB Output isn't correct
22 Halted 0 ms 0 KB -