oj.uz

Submission #639355

# Submission time Handle Problem Language Result Execution time Memory
639355 2022-09-09T15:49:22 Z PoonYaPat Boat (APIO16_boat) C++14
0 / 100
 241 ms 4436 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 222 ms 4300 KB Output is correct
2 Correct 220 ms 4216 KB Output is correct
3 Correct 241 ms 4272 KB Output is correct
4 Correct 215 ms 4436 KB Output is correct
5 Correct 235 ms 4300 KB Output is correct
6 Correct 137 ms 4300 KB Output is correct
7 Correct 131 ms 4296 KB Output is correct
8 Correct 131 ms 4304 KB Output is correct
9 Correct 137 ms 4284 KB Output is correct
10 Correct 133 ms 4252 KB Output is correct
11 Correct 131 ms 4224 KB Output is correct
12 Correct 138 ms 4304 KB Output is correct
13 Correct 131 ms 4288 KB Output is correct
14 Correct 132 ms 4208 KB Output is correct
15 Correct 135 ms 4280 KB Output is correct
16 Incorrect 46 ms 2916 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 4300 KB Output is correct
2 Correct 220 ms 4216 KB Output is correct
3 Correct 241 ms 4272 KB Output is correct
4 Correct 215 ms 4436 KB Output is correct
5 Correct 235 ms 4300 KB Output is correct
6 Correct 137 ms 4300 KB Output is correct
7 Correct 131 ms 4296 KB Output is correct
8 Correct 131 ms 4304 KB Output is correct
9 Correct 137 ms 4284 KB Output is correct
10 Correct 133 ms 4252 KB Output is correct
11 Correct 131 ms 4224 KB Output is correct
12 Correct 138 ms 4304 KB Output is correct
13 Correct 131 ms 4288 KB Output is correct
14 Correct 132 ms 4208 KB Output is correct
15 Correct 135 ms 4280 KB Output is correct
16 Incorrect 46 ms 2916 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 222 ms 4300 KB Output is correct
2 Correct 220 ms 4216 KB Output is correct
3 Correct 241 ms 4272 KB Output is correct
4 Correct 215 ms 4436 KB Output is correct
5 Correct 235 ms 4300 KB Output is correct
6 Correct 137 ms 4300 KB Output is correct
7 Correct 131 ms 4296 KB Output is correct
8 Correct 131 ms 4304 KB Output is correct
9 Correct 137 ms 4284 KB Output is correct
10 Correct 133 ms 4252 KB Output is correct
11 Correct 131 ms 4224 KB Output is correct
12 Correct 138 ms 4304 KB Output is correct
13 Correct 131 ms 4288 KB Output is correct
14 Correct 132 ms 4208 KB Output is correct
15 Correct 135 ms 4280 KB Output is correct
16 Incorrect 46 ms 2916 KB Output isn't correct
17 Halted 0 ms 0 KB -