Submission #38807

#	Time	Username	Problem	Language	Result	Execution time	Memory
38807		Waschbar	Boat (APIO16_boat)	C++14	0 / 100	1446 ms	524288 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 < unordered_map<int,int> > dp(1000);
vector < pair<int,int> > v(1000);
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> v[i].a >> v[i].b;
 
    unordered_map<int,int> :: iterator it;
    for(int i = 1; i <= n; i++){
        for(it = dp[i-1].begin(); it != dp[i-1].end(); it++)
            dp[i][it->first] = it->second;
 
        it = dp[i-1].begin();
        int x = v[i].a;
        int cnt = 0;
        while(it != dp[i-1].end()) {
            if(it->first >= x) break;
            dp[i][x] = (dp[i][x] + it->second) % MOD;
            cnt = (cnt + 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] + cnt) % MOD;
            if(it != dp[i-1].end() && it->first < j){
                dp[i][j] = (dp[i][j] + it->second) % MOD;
                cnt = (cnt + 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 <<" "<<dp[1][it->first]<< " - " << it->first << endl;
        it++;
    }
 
    cout << ans;
 
}

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