Submission #96009

#	Time	Username	Problem	Language	Result	Execution time	Memory
96009		oolimry	Boat (APIO16_boat)	C++14	9 / 100	33 ms	8312 KiB

boat

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;
long long mod = 1000000007;
//long long dp[505][2005];
int main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    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> k;
    for(set<long long>::iterator it = s.begin();it != s.end();it++){
        k.push_back(*it);
    }
    //cout << k.size() << endl;
    vector<ii> ranges;
    for(int i = 0;i < k.size();i++){
        ranges.push_back(ii(k[i],k[i]));
        if(i != 0){
            if(k[i] != k[i-1]+1){
                ranges.push_back(ii(k[i-1]+1,k[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;
        //cout << ranges[i].first << " " << ranges[i].second << "\n";
    }



    static long long dp[505][2005];

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

    for(int j = 0;j < m;j++){
        if(a[0] <= ranges[j].first && b[0] >= ranges[j].second){
            dp[0][j] = diff[j];
        }
    }
    for(int i = 1;i < n;i++){
        ///take nothing for this school
        for(int j = 0;j < m;j++){
            dp[i][j] += dp[i-1][j];
            dp[i][j] %= mod;
        }
        long long acc = 0ll;
        for(int j = 0;j < m;j++){
            if(j != 0) acc += dp[i-1][j-1];
            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[i][j] += x;
                dp[i][j] %= 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++){
        ans  += dp[n-1][j];
        ans %= mod;
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < k.size();i++){
                   ~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42