oj.uz

답안 #624381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624381 2022-08-08T05:41:11 Z socpite Boat (APIO16_boat) C++14
9 / 100
 1133 ms 14300 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(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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;
          	ll sum = 0;
            crr%=mod;
            for(int k = 2; k <= min({n, int(len), j}); k++){
                sum += crr;
                // C(k-2, j-2)*C(k, len)
                if(sum >= mod)pc[i][j]-=mod;
                crr=crr*(j-k)%mod*inv[k-1]%mod*(len-k)%mod*inv[k+1]%mod;
            }
          	pc[i][j]=sum;
        }
    }
    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;
                        if(dp[i][j] >= mod)dp[i][j]-=mod;
                      	if(dp[i][j] < 0)dp[i][j]+=mod;
                    }
                }
            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
            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:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     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

# 결과 실행 시간 메모리 Grader output
1 Correct 1116 ms 14092 KB Output is correct
2 Correct 1121 ms 14160 KB Output is correct
3 Correct 1121 ms 14300 KB Output is correct
4 Correct 1122 ms 14276 KB Output is correct
5 Correct 1119 ms 14068 KB Output is correct
6 Correct 1129 ms 14168 KB Output is correct
7 Correct 1120 ms 14120 KB Output is correct
8 Correct 1133 ms 14084 KB Output is correct
9 Correct 1129 ms 14156 KB Output is correct
10 Correct 1128 ms 14032 KB Output is correct
11 Correct 1131 ms 14096 KB Output is correct
12 Correct 1122 ms 14060 KB Output is correct
13 Correct 1130 ms 14196 KB Output is correct
14 Correct 1124 ms 14232 KB Output is correct
15 Correct 1122 ms 14252 KB Output is correct
16 Correct 203 ms 4332 KB Output is correct
17 Correct 215 ms 4548 KB Output is correct
18 Correct 208 ms 4520 KB Output is correct
19 Correct 217 ms 4508 KB Output is correct
20 Correct 209 ms 4508 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1116 ms 14092 KB Output is correct
2 Correct 1121 ms 14160 KB Output is correct
3 Correct 1121 ms 14300 KB Output is correct
4 Correct 1122 ms 14276 KB Output is correct
5 Correct 1119 ms 14068 KB Output is correct
6 Correct 1129 ms 14168 KB Output is correct
7 Correct 1120 ms 14120 KB Output is correct
8 Correct 1133 ms 14084 KB Output is correct
9 Correct 1129 ms 14156 KB Output is correct
10 Correct 1128 ms 14032 KB Output is correct
11 Correct 1131 ms 14096 KB Output is correct
12 Correct 1122 ms 14060 KB Output is correct
13 Correct 1130 ms 14196 KB Output is correct
14 Correct 1124 ms 14232 KB Output is correct
15 Correct 1122 ms 14252 KB Output is correct
16 Correct 203 ms 4332 KB Output is correct
17 Correct 215 ms 4548 KB Output is correct
18 Correct 208 ms 4520 KB Output is correct
19 Correct 217 ms 4508 KB Output is correct
20 Correct 209 ms 4508 KB Output is correct
21 Incorrect 316 ms 13036 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 1752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1116 ms 14092 KB Output is correct
2 Correct 1121 ms 14160 KB Output is correct
3 Correct 1121 ms 14300 KB Output is correct
4 Correct 1122 ms 14276 KB Output is correct
5 Correct 1119 ms 14068 KB Output is correct
6 Correct 1129 ms 14168 KB Output is correct
7 Correct 1120 ms 14120 KB Output is correct
8 Correct 1133 ms 14084 KB Output is correct
9 Correct 1129 ms 14156 KB Output is correct
10 Correct 1128 ms 14032 KB Output is correct
11 Correct 1131 ms 14096 KB Output is correct
12 Correct 1122 ms 14060 KB Output is correct
13 Correct 1130 ms 14196 KB Output is correct
14 Correct 1124 ms 14232 KB Output is correct
15 Correct 1122 ms 14252 KB Output is correct
16 Correct 203 ms 4332 KB Output is correct
17 Correct 215 ms 4548 KB Output is correct
18 Correct 208 ms 4520 KB Output is correct
19 Correct 217 ms 4508 KB Output is correct
20 Correct 209 ms 4508 KB Output is correct
21 Incorrect 316 ms 13036 KB Output isn't correct
22 Halted 0 ms 0 KB -