oj.uz

Submission #501403

# Submission time Handle Problem Language Result Execution time Memory
501403 2022-01-03T05:43:51 Z Abrar_Al_Samit Boat (APIO16_boat) C++17
0 / 100
 190 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;
const int MX = 501;
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.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -