답안 #501355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501355	2022-01-02T21:18:29 Z	Abrar_Al_Samit	Boat (APIO16_boat)	C++17	9 / 100	2000 ms	8204 KB

boat

#include<bits/stdc++.h>
using namespace std;
const int MX = 505;
const int Mod = 1e9 + 7;
int a[MX], b[MX];
map<tuple<int,int,int>,int>dp;
int n;
int solve(int i, int prev, int more) {
    if(i>n) return (prev!=0);
    if(dp.count(make_tuple(i, prev, more))) return dp[make_tuple(i, prev, more)]; 
    int ret = 0;
    ret = solve(i+1, prev, more);
    for(int cur=max(a[i], a[prev]+more+1); cur<=b[i]; ++cur) {
        ret += solve(i+1, i, cur-a[i]);
        if(ret>=Mod) ret -= Mod;
    }
    return dp[make_tuple(i, prev, more)] = ret;
}
void PlayGround() {
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> a[i] >> b[i];
    }   
    cout << solve(1, 0, 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	72 ms	8176 KB	Output is correct
2	Correct	82 ms	8112 KB	Output is correct
3	Correct	88 ms	8088 KB	Output is correct
4	Correct	71 ms	8112 KB	Output is correct
5	Correct	73 ms	8168 KB	Output is correct
6	Correct	77 ms	8088 KB	Output is correct
7	Correct	83 ms	8096 KB	Output is correct
8	Correct	116 ms	8188 KB	Output is correct
9	Correct	85 ms	8136 KB	Output is correct
10	Correct	87 ms	8204 KB	Output is correct
11	Correct	94 ms	8096 KB	Output is correct
12	Correct	86 ms	8124 KB	Output is correct
13	Correct	83 ms	8184 KB	Output is correct
14	Correct	86 ms	8124 KB	Output is correct
15	Correct	79 ms	8140 KB	Output is correct
16	Correct	75 ms	8196 KB	Output is correct
17	Correct	73 ms	8132 KB	Output is correct
18	Correct	73 ms	8116 KB	Output is correct
19	Correct	72 ms	8096 KB	Output is correct
20	Correct	72 ms	8132 KB	Output is correct

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	8176 KB	Output is correct
2	Correct	82 ms	8112 KB	Output is correct
3	Correct	88 ms	8088 KB	Output is correct
4	Correct	71 ms	8112 KB	Output is correct
5	Correct	73 ms	8168 KB	Output is correct
6	Correct	77 ms	8088 KB	Output is correct
7	Correct	83 ms	8096 KB	Output is correct
8	Correct	116 ms	8188 KB	Output is correct
9	Correct	85 ms	8136 KB	Output is correct
10	Correct	87 ms	8204 KB	Output is correct
11	Correct	94 ms	8096 KB	Output is correct
12	Correct	86 ms	8124 KB	Output is correct
13	Correct	83 ms	8184 KB	Output is correct
14	Correct	86 ms	8124 KB	Output is correct
15	Correct	79 ms	8140 KB	Output is correct
16	Correct	75 ms	8196 KB	Output is correct
17	Correct	73 ms	8132 KB	Output is correct
18	Correct	73 ms	8116 KB	Output is correct
19	Correct	72 ms	8096 KB	Output is correct
20	Correct	72 ms	8132 KB	Output is correct
21	Execution timed out	2071 ms	2292 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2064 ms	204 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	8176 KB	Output is correct
2	Correct	82 ms	8112 KB	Output is correct
3	Correct	88 ms	8088 KB	Output is correct
4	Correct	71 ms	8112 KB	Output is correct
5	Correct	73 ms	8168 KB	Output is correct
6	Correct	77 ms	8088 KB	Output is correct
7	Correct	83 ms	8096 KB	Output is correct
8	Correct	116 ms	8188 KB	Output is correct
9	Correct	85 ms	8136 KB	Output is correct
10	Correct	87 ms	8204 KB	Output is correct
11	Correct	94 ms	8096 KB	Output is correct
12	Correct	86 ms	8124 KB	Output is correct
13	Correct	83 ms	8184 KB	Output is correct
14	Correct	86 ms	8124 KB	Output is correct
15	Correct	79 ms	8140 KB	Output is correct
16	Correct	75 ms	8196 KB	Output is correct
17	Correct	73 ms	8132 KB	Output is correct
18	Correct	73 ms	8116 KB	Output is correct
19	Correct	72 ms	8096 KB	Output is correct
20	Correct	72 ms	8132 KB	Output is correct
21	Execution timed out	2071 ms	2292 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-