Submission #433808

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
433808	2021-06-20T11:00:20 Z	oscar1f	Boat (APIO16_boat)	C++17	9 / 100	2000 ms	8184 KB

boat

#include<bits/stdc++.h>
using namespace std;

const int MAX_ECOLE=501,INFINI=1000*1000*1000+7;
int nbEcole;
map<pair<int,int>,int> memo;
int mini[MAX_ECOLE],maxi[MAX_ECOLE];

int dyna(int idEcole,int maxMaint) {
    if (idEcole==nbEcole+1) {
        return 1;
    }
    int val=memo[make_pair(idEcole,maxMaint)];
    if (val!=0) {
        return val;
    }
    val=dyna(idEcole+1,maxMaint);
    for (int i=max(maxMaint+1,mini[idEcole]);i<=maxi[idEcole];i++) {
        val+=dyna(idEcole+1,i);
        val%=INFINI;
    }
    memo[make_pair(idEcole,maxMaint)]=val;
    return val;
}

int main() {
	ios_base::sync_with_stdio(false);
    cin>>nbEcole;
    for (int i=1;i<=nbEcole;i++) {
        cin>>mini[i]>>maxi[i];
    }
    cout<<(dyna(1,-1)+INFINI-1)%INFINI<<endl;
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	8132 KB	Output is correct
2	Correct	69 ms	8096 KB	Output is correct
3	Correct	79 ms	8112 KB	Output is correct
4	Correct	73 ms	8112 KB	Output is correct
5	Correct	57 ms	8152 KB	Output is correct
6	Correct	77 ms	8164 KB	Output is correct
7	Correct	70 ms	8148 KB	Output is correct
8	Correct	82 ms	8136 KB	Output is correct
9	Correct	74 ms	8124 KB	Output is correct
10	Correct	92 ms	8116 KB	Output is correct
11	Correct	94 ms	8128 KB	Output is correct
12	Correct	80 ms	8184 KB	Output is correct
13	Correct	77 ms	8180 KB	Output is correct
14	Correct	73 ms	8184 KB	Output is correct
15	Correct	77 ms	8104 KB	Output is correct
16	Correct	17 ms	2508 KB	Output is correct
17	Correct	18 ms	2676 KB	Output is correct
18	Correct	16 ms	2620 KB	Output is correct
19	Correct	17 ms	2640 KB	Output is correct
20	Correct	14 ms	2580 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	8132 KB	Output is correct
2	Correct	69 ms	8096 KB	Output is correct
3	Correct	79 ms	8112 KB	Output is correct
4	Correct	73 ms	8112 KB	Output is correct
5	Correct	57 ms	8152 KB	Output is correct
6	Correct	77 ms	8164 KB	Output is correct
7	Correct	70 ms	8148 KB	Output is correct
8	Correct	82 ms	8136 KB	Output is correct
9	Correct	74 ms	8124 KB	Output is correct
10	Correct	92 ms	8116 KB	Output is correct
11	Correct	94 ms	8128 KB	Output is correct
12	Correct	80 ms	8184 KB	Output is correct
13	Correct	77 ms	8180 KB	Output is correct
14	Correct	73 ms	8184 KB	Output is correct
15	Correct	77 ms	8104 KB	Output is correct
16	Correct	17 ms	2508 KB	Output is correct
17	Correct	18 ms	2676 KB	Output is correct
18	Correct	16 ms	2620 KB	Output is correct
19	Correct	17 ms	2640 KB	Output is correct
20	Correct	14 ms	2580 KB	Output is correct
21	Execution timed out	2067 ms	2944 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2069 ms	204 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	58 ms	8132 KB	Output is correct
2	Correct	69 ms	8096 KB	Output is correct
3	Correct	79 ms	8112 KB	Output is correct
4	Correct	73 ms	8112 KB	Output is correct
5	Correct	57 ms	8152 KB	Output is correct
6	Correct	77 ms	8164 KB	Output is correct
7	Correct	70 ms	8148 KB	Output is correct
8	Correct	82 ms	8136 KB	Output is correct
9	Correct	74 ms	8124 KB	Output is correct
10	Correct	92 ms	8116 KB	Output is correct
11	Correct	94 ms	8128 KB	Output is correct
12	Correct	80 ms	8184 KB	Output is correct
13	Correct	77 ms	8180 KB	Output is correct
14	Correct	73 ms	8184 KB	Output is correct
15	Correct	77 ms	8104 KB	Output is correct
16	Correct	17 ms	2508 KB	Output is correct
17	Correct	18 ms	2676 KB	Output is correct
18	Correct	16 ms	2620 KB	Output is correct
19	Correct	17 ms	2640 KB	Output is correct
20	Correct	14 ms	2580 KB	Output is correct
21	Execution timed out	2067 ms	2944 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-