oj.uz

Submission #639368

# Submission time Handle Problem Language Result Execution time Memory
639368 2022-09-09T16:37:55 Z PoonYaPat Boat (APIO16_boat) C++14
0 / 100
 251 ms 4324 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;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 4300 KB Output is correct
2 Correct 251 ms 4236 KB Output is correct
3 Correct 225 ms 4212 KB Output is correct
4 Correct 233 ms 4324 KB Output is correct
5 Correct 226 ms 4268 KB Output is correct
6 Correct 134 ms 4236 KB Output is correct
7 Correct 127 ms 4200 KB Output is correct
8 Correct 151 ms 4292 KB Output is correct
9 Correct 161 ms 4208 KB Output is correct
10 Correct 150 ms 4240 KB Output is correct
11 Correct 129 ms 4236 KB Output is correct
12 Correct 139 ms 4176 KB Output is correct
13 Correct 146 ms 4264 KB Output is correct
14 Correct 126 ms 4200 KB Output is correct
15 Correct 134 ms 4300 KB Output is correct
16 Incorrect 49 ms 2932 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 4300 KB Output is correct
2 Correct 251 ms 4236 KB Output is correct
3 Correct 225 ms 4212 KB Output is correct
4 Correct 233 ms 4324 KB Output is correct
5 Correct 226 ms 4268 KB Output is correct
6 Correct 134 ms 4236 KB Output is correct
7 Correct 127 ms 4200 KB Output is correct
8 Correct 151 ms 4292 KB Output is correct
9 Correct 161 ms 4208 KB Output is correct
10 Correct 150 ms 4240 KB Output is correct
11 Correct 129 ms 4236 KB Output is correct
12 Correct 139 ms 4176 KB Output is correct
13 Correct 146 ms 4264 KB Output is correct
14 Correct 126 ms 4200 KB Output is correct
15 Correct 134 ms 4300 KB Output is correct
16 Incorrect 49 ms 2932 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 226 ms 4300 KB Output is correct
2 Correct 251 ms 4236 KB Output is correct
3 Correct 225 ms 4212 KB Output is correct
4 Correct 233 ms 4324 KB Output is correct
5 Correct 226 ms 4268 KB Output is correct
6 Correct 134 ms 4236 KB Output is correct
7 Correct 127 ms 4200 KB Output is correct
8 Correct 151 ms 4292 KB Output is correct
9 Correct 161 ms 4208 KB Output is correct
10 Correct 150 ms 4240 KB Output is correct
11 Correct 129 ms 4236 KB Output is correct
12 Correct 139 ms 4176 KB Output is correct
13 Correct 146 ms 4264 KB Output is correct
14 Correct 126 ms 4200 KB Output is correct
15 Correct 134 ms 4300 KB Output is correct
16 Incorrect 49 ms 2932 KB Output isn't correct
17 Halted 0 ms 0 KB -