Submission #501405

#	Time	Username	Problem	Language	Result	Execution time	Memory
501405		Abrar_Al_Samit	Boat (APIO16_boat)	C++17	0 / 100	2011 ms	524288 KiB

boat

#include<bits/stdc++.h>
using namespace std;
const int MX = 101;
const int uMX = 1e6 + 1;
const int Mod = 1e9 + 7;
int a[MX], b[MX];
int dp[MX][uMX];
int n;
int solve(int i, int prev) {
    if(i>n) return (prev!=0);
    int &ret = dp[i][prev];
    if(ret!=-1) return ret;
    ret = solve(i+1, prev);
    for(int cur=max(a[i], prev+1); cur<=b[i]; ++cur) {
        ret += solve(i+1, cur);
        if(ret>=Mod) ret -= Mod;
    }
    return ret;
}
void PlayGround() {
    cin >> n;
    vector<tuple<int,int,int>>mapping;
    for(int i=1; i<=n; ++i) {
        cin >> a[i] >> b[i];
        mapping.emplace_back(a[i], b[i], i);
    }
    sort(mapping.begin(), mapping.end());
    int cur(1), sub(0);
    for(int i=0; i<n; ++i) {
        int f, s, id;
        tie(f, s, id) = mapping[i];
        if(f-sub>cur) {
            sub += f-sub-cur;
        }
        cur = max(cur, s-sub+1);
        a[id] = f-sub;
        b[id] = s-sub;
    }
    memset(dp, -1, sizeof dp);
    cout << solve(1, 0) << endl;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    PlayGround();
    return 0;
}

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