oj.uz

Submission #639363

# Submission time Handle Problem Language Result Execution time Memory
639363 2022-09-09T16:28:06 Z PoonYaPat Boat (APIO16_boat) C++14
0 / 100
 226 ms 4304 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 power(int a, int m) { //a^m;
    ll ans=1;
    while (m) {
        if (m%2==1) ans=(ans*a)%mod;
        a=(a*a)%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]=power(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];

            ll idx=1,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 226 ms 4248 KB Output is correct
2 Correct 224 ms 4196 KB Output is correct
3 Correct 225 ms 4228 KB Output is correct
4 Correct 219 ms 4248 KB Output is correct
5 Correct 222 ms 4296 KB Output is correct
6 Correct 130 ms 4304 KB Output is correct
7 Correct 130 ms 4300 KB Output is correct
8 Correct 127 ms 4224 KB Output is correct
9 Correct 131 ms 4172 KB Output is correct
10 Correct 133 ms 4280 KB Output is correct
11 Correct 133 ms 4268 KB Output is correct
12 Correct 134 ms 4244 KB Output is correct
13 Correct 125 ms 4300 KB Output is correct
14 Correct 119 ms 4192 KB Output is correct
15 Correct 129 ms 4272 KB Output is correct
16 Incorrect 47 ms 2948 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 4248 KB Output is correct
2 Correct 224 ms 4196 KB Output is correct
3 Correct 225 ms 4228 KB Output is correct
4 Correct 219 ms 4248 KB Output is correct
5 Correct 222 ms 4296 KB Output is correct
6 Correct 130 ms 4304 KB Output is correct
7 Correct 130 ms 4300 KB Output is correct
8 Correct 127 ms 4224 KB Output is correct
9 Correct 131 ms 4172 KB Output is correct
10 Correct 133 ms 4280 KB Output is correct
11 Correct 133 ms 4268 KB Output is correct
12 Correct 134 ms 4244 KB Output is correct
13 Correct 125 ms 4300 KB Output is correct
14 Correct 119 ms 4192 KB Output is correct
15 Correct 129 ms 4272 KB Output is correct
16 Incorrect 47 ms 2948 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 4248 KB Output is correct
2 Correct 224 ms 4196 KB Output is correct
3 Correct 225 ms 4228 KB Output is correct
4 Correct 219 ms 4248 KB Output is correct
5 Correct 222 ms 4296 KB Output is correct
6 Correct 130 ms 4304 KB Output is correct
7 Correct 130 ms 4300 KB Output is correct
8 Correct 127 ms 4224 KB Output is correct
9 Correct 131 ms 4172 KB Output is correct
10 Correct 133 ms 4280 KB Output is correct
11 Correct 133 ms 4268 KB Output is correct
12 Correct 134 ms 4244 KB Output is correct
13 Correct 125 ms 4300 KB Output is correct
14 Correct 119 ms 4192 KB Output is correct
15 Correct 129 ms 4272 KB Output is correct
16 Incorrect 47 ms 2948 KB Output isn't correct
17 Halted 0 ms 0 KB -