oj.uz

답안 #47970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47970 2018-05-09T09:31:58 Z 3zp Boat (APIO16_boat) C++14
0 / 100
 128 ms 6392 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 (int 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]);
            ll L = d[j].second - d[j].first + 1;
            ll W = 1;
            for (ll t = j; t >= 0; t--){
                if(l[i] > j|| r[i] < j) break;
                W = W*(L - (j -t)) % mod *in[j-t+1] % mod;
                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] << 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 32 ms 6392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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