oj.uz

Submission #118608

# Submission time Handle Problem Language Result Execution time Memory
118608 2019-06-19T09:44:56 Z pzdba Boat (APIO16_boat) C++14
27 / 100
 132 ms 4216 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
vector<int> h;
int a[505], b[505], l[505];
LL dp[505][1005];
LL inv[505];
LL go(LL a, LL b){
    LL ans=1;
    while(b){
        if(b%2) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i=0;i<=n;i++) inv[i] = go(i, mod-2);

    for(int i=1;i<=n;i++){
        scanf("%d%d", &a[i], &b[i]);
        h.push_back(a[i]-1);
        h.push_back(b[i]);
    }   
    sort(h.begin(), h.end());
    h.erase(unique(h.begin(), h.end()), h.end());
    for(int i=1;i<=n;i++){
        a[i] = lower_bound(h.begin(), h.end(), a[i]-1) - h.begin() + 1;
        b[i] = lower_bound(h.begin(), h.end(), b[i]) - h.begin() + 1;
    }
    l[1] = h[0];
    for(int i=2;i<=h.size();i++) l[i] = h[i-1] - h[i-2];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=h.size();j++){
            if(i == 1){
                if(a[i] < j && j <= b[i]) dp[i][j] = (dp[i][j] + l[j])%mod;
            }
            else{
                if(a[i] < j && j <= b[i]){
                    dp[i][j] = (dp[i][j] + l[j] + l[j]*dp[i-1][j-1])%mod;
                    int cnt = 1;
                    LL sum = l[j]-1;
                    for(int k=i-1;k>=1;k--){
                        if(a[k] < j && j <= b[k]){
                            cnt++;
                            sum = sum*(l[j]+cnt-2)%mod*inv[cnt]%mod;
                            dp[i][j] = (dp[i][j] + sum + sum*dp[k-1][j-1])%mod;
                        }
                    }
                }
            }
            dp[i][j] = (dp[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + mod)%mod;
        }
    }
    printf("%lld\n", dp[n][h.size()]);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=2;i<=h.size();i++) l[i] = h[i-1] - h[i-2];
                 ~^~~~~~~~~~
boat.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<=h.size();j++){
                     ~^~~~~~~~~~
boat.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 4 ms 896 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 7 ms 896 KB Output is correct
8 Correct 7 ms 896 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 7 ms 896 KB Output is correct
11 Correct 5 ms 896 KB Output is correct
12 Correct 4 ms 896 KB Output is correct
13 Correct 5 ms 896 KB Output is correct
14 Correct 5 ms 896 KB Output is correct
15 Correct 5 ms 896 KB Output is correct
16 Correct 4 ms 768 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 768 KB Output is correct
19 Correct 4 ms 896 KB Output is correct
20 Correct 5 ms 896 KB Output is correct

Subtask #4
0 / 42.0

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