제출 #38780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38780		Waschbar	Boat (APIO16_boat)	C++14	9 / 100	2000 ms	291236 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() {

    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;

    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: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42