oj.uz

Submission #639371

# Submission time Handle Problem Language Result Execution time Memory
639371 2022-09-09T16:39:21 Z PoonYaPat Boat (APIO16_boat) C++14
0 / 100
 227 ms 4380 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const ll mod=1e9+7;
ll n,c[1001],st[501],ed[501],cnt,comb[501];
ll dp[501][1001];
set<int> ss;
 
ll pow(int a, int m) { //a^m;
    ll val=a,ans=1;
    while (m) {
        if (m%2==1) ans=(ans*val)%mod;
        val=(val*val)%mod;
        m/=2;
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) {
        cin>>st[i]>>ed[i]; --st[i];
        ss.insert(st[i]);
        ss.insert(ed[i]);
    }
 
    for (int i=1; i<=n; ++i) comb[i]=pow(i,mod-2);
 
    cnt=ss.size()-1;
    int id=0;
    for (auto it=ss.begin(); it!=ss.end(); ++it) c[id++]=*it;
 
    for (int i=0; i<=cnt; ++i) dp[0][i]=1;
 
    for (int i=1; i<=n; ++i) {
        dp[i][0]=1; //don't send any boat
 
        for (int j=1; j<=cnt; ++j) { //consider from the range from c[j-1]+1 to c[j]
            dp[i][j]=dp[i][j-1];
 
            int idx=1;
            ll com=1;
            for (auto k=i; k>0; --k) {
                if (st[k]<c[j] && c[j]<=ed[k]) {
                    com=((com*(c[j]-c[j-1]+idx-1)%mod)*comb[idx])%mod;
                    dp[i][j]=(dp[i][j]+dp[k-1][j-1]*com)%mod;
                    ++idx;
                }
            }
        }
    }
    cout<<(dp[n][cnt]-1+mod)%mod;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4184 KB Output is correct
2 Correct 222 ms 4276 KB Output is correct
3 Correct 217 ms 4236 KB Output is correct
4 Correct 213 ms 4208 KB Output is correct
5 Correct 216 ms 4292 KB Output is correct
6 Correct 129 ms 4264 KB Output is correct
7 Correct 134 ms 4260 KB Output is correct
8 Correct 128 ms 4300 KB Output is correct
9 Correct 137 ms 4380 KB Output is correct
10 Correct 138 ms 4216 KB Output is correct
11 Correct 132 ms 4260 KB Output is correct
12 Correct 132 ms 4268 KB Output is correct
13 Correct 127 ms 4188 KB Output is correct
14 Correct 122 ms 4244 KB Output is correct
15 Correct 130 ms 4208 KB Output is correct
16 Incorrect 48 ms 2928 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4184 KB Output is correct
2 Correct 222 ms 4276 KB Output is correct
3 Correct 217 ms 4236 KB Output is correct
4 Correct 213 ms 4208 KB Output is correct
5 Correct 216 ms 4292 KB Output is correct
6 Correct 129 ms 4264 KB Output is correct
7 Correct 134 ms 4260 KB Output is correct
8 Correct 128 ms 4300 KB Output is correct
9 Correct 137 ms 4380 KB Output is correct
10 Correct 138 ms 4216 KB Output is correct
11 Correct 132 ms 4260 KB Output is correct
12 Correct 132 ms 4268 KB Output is correct
13 Correct 127 ms 4188 KB Output is correct
14 Correct 122 ms 4244 KB Output is correct
15 Correct 130 ms 4208 KB Output is correct
16 Incorrect 48 ms 2928 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 4184 KB Output is correct
2 Correct 222 ms 4276 KB Output is correct
3 Correct 217 ms 4236 KB Output is correct
4 Correct 213 ms 4208 KB Output is correct
5 Correct 216 ms 4292 KB Output is correct
6 Correct 129 ms 4264 KB Output is correct
7 Correct 134 ms 4260 KB Output is correct
8 Correct 128 ms 4300 KB Output is correct
9 Correct 137 ms 4380 KB Output is correct
10 Correct 138 ms 4216 KB Output is correct
11 Correct 132 ms 4260 KB Output is correct
12 Correct 132 ms 4268 KB Output is correct
13 Correct 127 ms 4188 KB Output is correct
14 Correct 122 ms 4244 KB Output is correct
15 Correct 130 ms 4208 KB Output is correct
16 Incorrect 48 ms 2928 KB Output isn't correct
17 Halted 0 ms 0 KB -