oj.uz

답안 #139298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139298 2019-07-31T14:19:47 Z 3zp Boat (APIO16_boat) C++14
0 / 100
 15 ms 6264 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[5009], b[5009];
ll mod = 1e9+7;
ll c[2009];
ll l[5009], r[5009];
ll dp[5009][4009];
ll in[5009];
vector<pair<ll,ll> > d;
main(){
    ll n;
    cin >> n;
    for(ll i = 0; i < n; i++){
        cin >> a[i] >> b[i];
        c[2*i] = a[i];
        c[2*i + 1] = b[i];
    }
    sort(c, c+2*n);
    in[0] = 1;
    in[1] = 1;
    for (ll i = 2; i <= n; i++)
        in[i] = in[mod % i] *(mod - mod / i) % mod;
    for(ll i = 0; i < 2*n; i++){
        if(i < 2*n-1 && c[i] == c[i+1]) continue;
        d.push_back({c[i], c[i]});
        if(i == 2*n-1 || c[i+1] == c[i]+1) continue;
        d.push_back({c[i]+1, c[i+1]-1});
    }
    for (ll i= 0; i < n; i++){
        for (ll j = 0; j < d.size(); j++){
            if(a[i] == d[j].first) {l[i] = j; break;}
        }
        for (ll j = 0; j < d.size(); j++){
            if(b[i] == d[j].second) r[i] = j;
        }
    }
    ll N = d.size();
    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < N; j++){
            if(j) dp[i][j] = (dp[i][j-1]);
          else dp[i][j] = 1;
            ll L = d[j].second - d[j].first + 1;
            ll W = 1;
            for (ll t = i; t >= 0; t--){
                if(l[t] > j || r[t] < j) break;
                W = (W*(L - (i -t)) % mod )*in[i-t+1] % mod;
                if(!W) break;
                if(t == 0) dp[i][j] = (dp[i][j] + W) % mod; else
                if(j == 0) dp[i][j] = (dp[i][j] + W) % mod; else
                dp[i][j] = (dp[i][j] + W*dp[t-1][j-1]) % mod;
 
            }
        }
 
        for(ll j = 0; j < N; j++){
 
            if(i) dp[i][j] = (dp[i][j] + dp[i-1][j]) % mod;
            else dp[i][j] = (dp[i][j] + 1) % mod;
        }
    }
    cout << (dp[n-1][N-1] -1 + mod)% mod << endl;
    return 0;
}

Compilation message

boat.cpp:11:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
boat.cpp: In function 'int main()':
boat.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j < d.size(); j++){
                        ~~^~~~~~~~~~
boat.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (ll j = 0; j < d.size(); j++){
                        ~~^~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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