Submission #38777

#	Time	Username	Problem	Language	Result	Execution time	Memory
38777		Waschbar	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	189724 KiB

boat

#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;

const long long INF = 1e18;
const int MOD = 1e9+7;

int n;
vector < map<int,int> > dp(1000);
vector < pair<int,int> > v(1000);

int main() {

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i].a >> v[i].b;

    map<int,int> :: iterator it;
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i-1];
        it = dp[i-1].begin();
        int x = v[i].a;
        while(it != dp[i-1].end()) {
            if(it->first >= x) break;
            dp[i][x] = (dp[i][x] + it->second) % MOD;
            it++;
        }
        if(it != dp[i-1].end())
            it++;

        for(int j = v[i].a+1; j <= v[i].b; j++){
            dp[i][j] = dp[i][j-1];
            if(it != dp[i-1].end() && it->first < j){
                dp[i][j] = (dp[i][j] + it->second) % MOD;
                it++;
            }
        }

        for(int j = v[i].a; j <= v[i].b; j++)
            dp[i][j] = (dp[i][j]+1) % MOD;

    }

    it = dp[n].begin();
    int ans = 0;
    while(it != dp[n].end()) {
        ans = (ans+(it->second)) % MOD;
        //cout << it->second << " " << it->first << endl;
        it++;
    }

    cout << ans;

}

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