oj.uz

답안 #96114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96114 2019-02-06T03:52:26 Z oolimry Boat (APIO16_boat) C++14
27 / 100
 2000 ms 8312 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;
long long mod = 1000000007;
//long long dp[505][2005];
//static long long dp[505][2005][505];
#define int long long
long long modInverse(long long a, long long m)
{
    long long m0 = m;
    long long y = 0, x = 1;

    if (m == 1)
      return 0;

    while (a > 1)
    {
        // q is quotient
        long long q = a / m;
        long long t = m;

        // m is remainder now, process same as
        // Euclid's algo
        m = a % m, a = t;
        t = y;

        // Update y and x
        y = x - q * y;
        x = t;
    }

    // Make x positive
    if (x < 0)
       x += m0;

    return x;
}
main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    long long inverse[505];
    for(long long i = 1;i < 505;i++){
        inverse[i] = modInverse(i,mod);
    }
    int n;
    cin >> n;
    long long a[n];
    long long b[n];
    set<long long> s;
    for(int i = 0;i < n;i++){
        cin >> a[i] >> b[i];
        s.insert(a[i]);
        s.insert(b[i]);
    }
    //cout << s.size() << endl;
    vector<long long> key;
    for(set<long long>::iterator it = s.begin();it != s.end();it++){
        key.push_back(*it);
    }
    //cout << k.size() << endl;
    vector<ii> ranges;
    for(int i = 0;i < key.size();i++){
        ranges.push_back(ii(key[i],key[i]));
        if(i != 0){
            if(key[i] != key[i-1]+1){
                ranges.push_back(ii(key[i-1]+1,key[i]-1));
            }
        }
    }
    sort(ranges.begin(),ranges.end());
    int m = ranges.size();
    //cout << m << "\n";
    long long diff[m];
    for(int i = 0;i < m;i++){
        diff[i] = ranges[i].second - ranges[i].first + 1;
        diff[i] %= mod;
        //cout << ranges[i].first << " " << ranges[i].second << "\n";
    }



    static long long dp[2][2005][505];
    //boat no, range, number taken b4;

    for(int i = 0;i < 2;i++){
        for(int j = 0;j < m;j++){
            for(int k = 0;k < 505;k++){
                dp[i][j][k] = 0ll;
            }
        }
    }


    for(int j = 0;j < m;j++){
        if(a[0] <= ranges[j].first && b[0] >= ranges[j].second){
            dp[0][j][1] = diff[j];
            //cout << a[0] << " " << ranges[j].first << " " << ranges[j].second << " " << b[0] << endl;
        }
    }

    for(int i = 1;i < n;i++){
        ///take nothing for this school
        int ii = i % 2;
        for(int j = 0;j < m;j++){
            for(int k = 1;k < 505;k++){
                dp[ii][j][k] = dp[ii^1][j][k];
                dp[ii][j][k] %= mod;
            }
        }

        ///take same as previous school
        for(int j = 0;j < m;j++){
            if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){
                for(int k = 2;k < 505;k++){
                    long long x = dp[ii^1][j][k-1];
                    if(diff[j] - k + 1 <= 0) break;
                    x *= (diff[j] - k + 1);
                    x %= mod;
                    x *= inverse[k];
                    x %= mod;
                    dp[ii][j][k] += x;
                    //dp[ii][j][k] %= mod;
                }
            }
        }

        ///take for the first time

        long long acc = 0ll;
        for(int j = 0;j < m;j++){
            if(j != 0){
                for(int k = 1;k < 505;k++){
                    acc += dp[ii^1][j-1][k];
                    acc %= mod;
                }
            }
            if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){
                long long x = acc;
                x += 1;
                x *= diff[j];
                acc %= mod;
                dp[ii][j][1] += x;
                dp[ii][j][1] %= mod;
            }
        }

    }

/*
    for(int j = 0;j < m;j++){
        cout << ranges[j].first << " " << ranges[j].second << ": ";
        for(int i = 0;i < n;i++){
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
*/
    long long ans = 0ll;
    for(int j = 0;j < m;j++){
        for(int k = 1;k < 505;k++){
            ans += dp[(n-1)%2][j][k];
            ans %= mod;
            if(dp[(n-1)%2][j][k] != 0){
                //cout << j << " " << k << " " << dp[(n-1)%2][j][k] << "\n";
            }
        }
    }
    cout << ans;

    return 0;
}

Compilation message

boat.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
boat.cpp: In function 'int main()':
boat.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < key.size();i++){
                   ~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 8312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 8312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 576 ms 3576 KB Output is correct
2 Correct 563 ms 3576 KB Output is correct
3 Correct 581 ms 3576 KB Output is correct
4 Correct 600 ms 3576 KB Output is correct
5 Correct 586 ms 3448 KB Output is correct
6 Correct 621 ms 3704 KB Output is correct
7 Correct 633 ms 3576 KB Output is correct
8 Correct 618 ms 3576 KB Output is correct
9 Correct 621 ms 3576 KB Output is correct
10 Correct 618 ms 3676 KB Output is correct
11 Correct 589 ms 3704 KB Output is correct
12 Correct 565 ms 3448 KB Output is correct
13 Correct 573 ms 3576 KB Output is correct
14 Correct 589 ms 3576 KB Output is correct
15 Correct 592 ms 3576 KB Output is correct
16 Correct 250 ms 1784 KB Output is correct
17 Correct 248 ms 1784 KB Output is correct
18 Correct 266 ms 1784 KB Output is correct
19 Correct 252 ms 1784 KB Output is correct
20 Correct 268 ms 1784 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2074 ms 8312 KB Time limit exceeded
2 Halted 0 ms 0 KB -