Submission #433877

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

boat

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

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

int dyna(int idEcole,int maxMaint) {
    if (idEcole==nbEcole+1) {
        return 1;
    }
    if (maxMaint<mini[idEcole]) {
        return memo[(long long)idEcole*(long long)INFINI+(long long)maxMaint]=(dyna(idEcole+1,maxMaint)+dyna(idEcole,mini[idEcole]))%INFINI;
    }
    int val=memo[(long long)idEcole*(long long)INFINI+(long long)maxMaint];
    if (val!=0) {
        return val;
    }
    val=dyna(idEcole+1,maxMaint);
    if (maxMaint<maxi[idEcole]) {
        val+=dyna(idEcole,maxMaint+1);
        val%=INFINI;
    }
    memo[(long long)idEcole*(long long)INFINI+(long long)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	53 ms	8164 KB	Output is correct
2	Correct	52 ms	8088 KB	Output is correct
3	Correct	51 ms	8160 KB	Output is correct
4	Correct	53 ms	8228 KB	Output is correct
5	Correct	51 ms	8132 KB	Output is correct
6	Correct	55 ms	8204 KB	Output is correct
7	Correct	49 ms	8120 KB	Output is correct
8	Correct	54 ms	8104 KB	Output is correct
9	Correct	56 ms	8172 KB	Output is correct
10	Correct	59 ms	8192 KB	Output is correct
11	Correct	64 ms	8112 KB	Output is correct
12	Correct	52 ms	8128 KB	Output is correct
13	Correct	59 ms	8132 KB	Output is correct
14	Correct	51 ms	8120 KB	Output is correct
15	Correct	56 ms	8100 KB	Output is correct
16	Correct	16 ms	2508 KB	Output is correct
17	Correct	14 ms	2764 KB	Output is correct
18	Correct	17 ms	2660 KB	Output is correct
19	Correct	13 ms	2636 KB	Output is correct
20	Correct	11 ms	2508 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	8164 KB	Output is correct
2	Correct	52 ms	8088 KB	Output is correct
3	Correct	51 ms	8160 KB	Output is correct
4	Correct	53 ms	8228 KB	Output is correct
5	Correct	51 ms	8132 KB	Output is correct
6	Correct	55 ms	8204 KB	Output is correct
7	Correct	49 ms	8120 KB	Output is correct
8	Correct	54 ms	8104 KB	Output is correct
9	Correct	56 ms	8172 KB	Output is correct
10	Correct	59 ms	8192 KB	Output is correct
11	Correct	64 ms	8112 KB	Output is correct
12	Correct	52 ms	8128 KB	Output is correct
13	Correct	59 ms	8132 KB	Output is correct
14	Correct	51 ms	8120 KB	Output is correct
15	Correct	56 ms	8100 KB	Output is correct
16	Correct	16 ms	2508 KB	Output is correct
17	Correct	14 ms	2764 KB	Output is correct
18	Correct	17 ms	2660 KB	Output is correct
19	Correct	13 ms	2636 KB	Output is correct
20	Correct	11 ms	2508 KB	Output is correct
21	Correct	1326 ms	161092 KB	Output is correct
22	Correct	1221 ms	161220 KB	Output is correct
23	Correct	1275 ms	161416 KB	Output is correct
24	Correct	1251 ms	161684 KB	Output is correct
25	Correct	1283 ms	162980 KB	Output is correct
26	Correct	962 ms	101440 KB	Output is correct
27	Correct	1084 ms	112804 KB	Output is correct
28	Correct	1172 ms	113736 KB	Output is correct
29	Correct	1128 ms	111684 KB	Output is correct
30	Execution timed out	2101 ms	181424 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1193 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	Correct	53 ms	8164 KB	Output is correct
2	Correct	52 ms	8088 KB	Output is correct
3	Correct	51 ms	8160 KB	Output is correct
4	Correct	53 ms	8228 KB	Output is correct
5	Correct	51 ms	8132 KB	Output is correct
6	Correct	55 ms	8204 KB	Output is correct
7	Correct	49 ms	8120 KB	Output is correct
8	Correct	54 ms	8104 KB	Output is correct
9	Correct	56 ms	8172 KB	Output is correct
10	Correct	59 ms	8192 KB	Output is correct
11	Correct	64 ms	8112 KB	Output is correct
12	Correct	52 ms	8128 KB	Output is correct
13	Correct	59 ms	8132 KB	Output is correct
14	Correct	51 ms	8120 KB	Output is correct
15	Correct	56 ms	8100 KB	Output is correct
16	Correct	16 ms	2508 KB	Output is correct
17	Correct	14 ms	2764 KB	Output is correct
18	Correct	17 ms	2660 KB	Output is correct
19	Correct	13 ms	2636 KB	Output is correct
20	Correct	11 ms	2508 KB	Output is correct
21	Correct	1326 ms	161092 KB	Output is correct
22	Correct	1221 ms	161220 KB	Output is correct
23	Correct	1275 ms	161416 KB	Output is correct
24	Correct	1251 ms	161684 KB	Output is correct
25	Correct	1283 ms	162980 KB	Output is correct
26	Correct	962 ms	101440 KB	Output is correct
27	Correct	1084 ms	112804 KB	Output is correct
28	Correct	1172 ms	113736 KB	Output is correct
29	Correct	1128 ms	111684 KB	Output is correct
30	Execution timed out	2101 ms	181424 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-