oj.uz

Submission #399047

# Submission time Handle Problem Language Result Execution time Memory
399047 2021-05-05T07:51:43 Z oolimry Boat (APIO16_boat) C++17
0 / 100
 3 ms 332 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;
long long mod = 1000000007;


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;
}
static long long a[505];
static long long b[505];
static long long inverse[505];
static ii ranges[1010];
static long long diff[1010];
static long long posa[505];
static long long posb[505];
static long long dp[2][2005][505];
static long long acc[1010];
int main()
{
    freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(long long i = 1;i < 505;i++){
        inverse[i] = modInverse(i,mod);
    }
    int n;
    cin >> n;


    vector<long long> s;
    for(int i = 0;i < n;i++){
        cin >> a[i] >> b[i];
        s.push_back(a[i]);
        s.push_back(b[i]+1);
    }
    //cout << s.size() << endl;
    sort(s.begin(),s.end());
    s.erase(unique(s.begin(),s.end()),s.end());
    vector<long long> key;
    for(int i = 0;i < s.size();i++){
        key.push_back(s[i]);
    }
    //cout << k.size() << endl;
    int m = key.size() - 1;

    for(int i = 0;i < m;i++){
        ranges[i] = (ii(key[i],key[i+1]-1));
    }
    //sort(ranges,ranges + m);

    //cout << m << "\n";

    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";
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(ranges[j].first == a[i]) posa[i] = j;
            if(ranges[j].second == b[i]) posb[i] = j;
        }
    }

    for(int j = posa[0];j <= posb[0];j++){
        dp[0][j][1] = diff[j];
    }

    for(int i = 1;i < n;i++){

        fill(acc,acc+m,0);
        ///take nothing for this school
        int ii = i % 2;
        for(int j = 0;j < m;j++){
            for(int k = 1;k < 505;k++){
                long long y = dp[ii^1][j][k];
                if(y == 0) break;
                dp[ii][j][k] = y;
                //dp[ii][j][k] %= mod;
                acc[j] += y;
                acc[j] %= mod;
            }
            if(j!=0){
                acc[j] += acc[j-1];
                acc[j] %= mod;
            }
        }


        ///take same as previous school
        for(int j = posa[i];j <= posb[i];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(x == 0) break;
                    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 = posa[i];j <= posb[i];j++){
            if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){
                long long x;
                if(j == 0) x = 0;
                else x = acc[j-1];
                x += 1;
                x *= diff[j];
                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;
        }
    }
    cout << ans;

    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0;i < s.size();i++){
      |                   ~~^~~~~~~~~~
boat.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |     freopen("i.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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