답안 #501400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501400	2022-01-03T05:42:30 Z	Abrar_Al_Samit	Boat (APIO16_boat)	C++17	9 / 100	2000 ms	40516 KB

boat

#include<bits/stdc++.h>
using namespace std;
const int MX = 505;
const int uMX = 1e4 + 3;
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

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	20044 KB	Output is correct
2	Correct	9 ms	20032 KB	Output is correct
3	Correct	9 ms	20044 KB	Output is correct
4	Correct	10 ms	20044 KB	Output is correct
5	Correct	9 ms	20140 KB	Output is correct
6	Correct	9 ms	20016 KB	Output is correct
7	Correct	10 ms	20044 KB	Output is correct
8	Correct	9 ms	20044 KB	Output is correct
9	Correct	10 ms	20044 KB	Output is correct
10	Correct	10 ms	20044 KB	Output is correct
11	Correct	10 ms	20048 KB	Output is correct
12	Correct	9 ms	20044 KB	Output is correct
13	Correct	10 ms	20036 KB	Output is correct
14	Correct	9 ms	20040 KB	Output is correct
15	Correct	11 ms	20036 KB	Output is correct
16	Correct	9 ms	20052 KB	Output is correct
17	Correct	9 ms	20052 KB	Output is correct
18	Correct	9 ms	20072 KB	Output is correct
19	Correct	9 ms	20044 KB	Output is correct
20	Correct	8 ms	20100 KB	Output is correct

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	20044 KB	Output is correct
2	Correct	9 ms	20032 KB	Output is correct
3	Correct	9 ms	20044 KB	Output is correct
4	Correct	10 ms	20044 KB	Output is correct
5	Correct	9 ms	20140 KB	Output is correct
6	Correct	9 ms	20016 KB	Output is correct
7	Correct	10 ms	20044 KB	Output is correct
8	Correct	9 ms	20044 KB	Output is correct
9	Correct	10 ms	20044 KB	Output is correct
10	Correct	10 ms	20044 KB	Output is correct
11	Correct	10 ms	20048 KB	Output is correct
12	Correct	9 ms	20044 KB	Output is correct
13	Correct	10 ms	20036 KB	Output is correct
14	Correct	9 ms	20040 KB	Output is correct
15	Correct	11 ms	20036 KB	Output is correct
16	Correct	9 ms	20052 KB	Output is correct
17	Correct	9 ms	20052 KB	Output is correct
18	Correct	9 ms	20072 KB	Output is correct
19	Correct	9 ms	20044 KB	Output is correct
20	Correct	8 ms	20100 KB	Output is correct
21	Execution timed out	2066 ms	20044 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1624 ms	40516 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	20044 KB	Output is correct
2	Correct	9 ms	20032 KB	Output is correct
3	Correct	9 ms	20044 KB	Output is correct
4	Correct	10 ms	20044 KB	Output is correct
5	Correct	9 ms	20140 KB	Output is correct
6	Correct	9 ms	20016 KB	Output is correct
7	Correct	10 ms	20044 KB	Output is correct
8	Correct	9 ms	20044 KB	Output is correct
9	Correct	10 ms	20044 KB	Output is correct
10	Correct	10 ms	20044 KB	Output is correct
11	Correct	10 ms	20048 KB	Output is correct
12	Correct	9 ms	20044 KB	Output is correct
13	Correct	10 ms	20036 KB	Output is correct
14	Correct	9 ms	20040 KB	Output is correct
15	Correct	11 ms	20036 KB	Output is correct
16	Correct	9 ms	20052 KB	Output is correct
17	Correct	9 ms	20052 KB	Output is correct
18	Correct	9 ms	20072 KB	Output is correct
19	Correct	9 ms	20044 KB	Output is correct
20	Correct	8 ms	20100 KB	Output is correct
21	Execution timed out	2066 ms	20044 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-