Submission #38776

#	Time	Username	Problem	Language	Result	Execution time	Memory
38776		Waschbar	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	180220 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];
        for(int j = v[i].a; j <= v[i].b; j++) {
            it = dp[i-1].begin();
            while(it != dp[i-1].end()) {
                if(it->first >= j) break;
                dp[i][j] = (dp[i][j] + it->second) % MOD;
                it++;
            }
            //if(i != n)
                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