oj.uz

Submission #152793

# Submission time Handle Problem Language Result Execution time Memory
152793 2019-09-09T14:11:18 Z mhy908 Boat (APIO16_boat) C++14
0 / 100
 10 ms 2300 KB 
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define llinf 8987654321987654321
#define mod 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
vector<LL> id;
int n;
LL a[510], b[510];
LL dp[510][510], sum[510][510], inv[510], len[1010];
LL power(LL a, LL b)
{
    if(!b)return 1;
    LL ret=power(a, b/2);
    return b%2?ret*ret%mod*a:ret*ret%mod;
}
int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)inv[i]=power(i, mod-2);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &a[i], &b[i]);
        id.pb(a[i]-1);
        id.pb(b[i]);
    }
    sort(all(id));
    id.erase(unique(all(id)), id.end());
    for(int i=1; i<=n; i++){
        LL temp=lower_bound(all(id), a[i]-1)+1-id.begin();
        a[i]=temp;
        temp=lower_bound(all(id), b[i])+1-id.begin();
        b[i]=temp;
    }
    int siz=id.size();
    len[1]=id[0];
    for(int i=1; i<=siz; i++)len[i]=id[i-1]-id[i-2];
    for(int i=1;i<=n;i++){
        for(int j=1; j<=siz; j++){
            if(i==1&&a[i]<j&&j<=b[i])dp[i][j]=(dp[i][j]+len[j])%mod;
            else{
                if(a[i]<j&&j<=b[i]){
                    dp[i][j]=(dp[i][j]+len[j]*(1+dp[i-1][j-1]))%mod;
                    int cnt=1;
                    LL sum=len[j]-1;
                    for(int k=i-1; k>=1; k--){
                        if(a[k]<j&&j<=b[k]){
                            cnt++;
                            sum=sum*(len[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", dp[n][siz]);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:22: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("%lld %lld", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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