Submission #433815

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

boat

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

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

int dyna(int idEcole,int maxMaint) {
    if (idEcole==nbEcole+1) {
        return 1;
    }
    int val=memo[(long long)idEcole*(long long)INFINI+(long long)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[(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	30 ms	5556 KB	Output is correct
2	Correct	31 ms	5548 KB	Output is correct
3	Correct	30 ms	5596 KB	Output is correct
4	Correct	26 ms	5596 KB	Output is correct
5	Correct	29 ms	5560 KB	Output is correct
6	Correct	27 ms	5564 KB	Output is correct
7	Correct	31 ms	5652 KB	Output is correct
8	Correct	25 ms	5600 KB	Output is correct
9	Correct	29 ms	5716 KB	Output is correct
10	Correct	25 ms	5620 KB	Output is correct
11	Correct	25 ms	5560 KB	Output is correct
12	Correct	25 ms	5620 KB	Output is correct
13	Correct	27 ms	5536 KB	Output is correct
14	Correct	26 ms	5568 KB	Output is correct
15	Correct	26 ms	5536 KB	Output is correct
16	Correct	6 ms	1760 KB	Output is correct
17	Correct	8 ms	1832 KB	Output is correct
18	Correct	7 ms	1832 KB	Output is correct
19	Correct	6 ms	1832 KB	Output is correct
20	Correct	6 ms	1820 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	5556 KB	Output is correct
2	Correct	31 ms	5548 KB	Output is correct
3	Correct	30 ms	5596 KB	Output is correct
4	Correct	26 ms	5596 KB	Output is correct
5	Correct	29 ms	5560 KB	Output is correct
6	Correct	27 ms	5564 KB	Output is correct
7	Correct	31 ms	5652 KB	Output is correct
8	Correct	25 ms	5600 KB	Output is correct
9	Correct	29 ms	5716 KB	Output is correct
10	Correct	25 ms	5620 KB	Output is correct
11	Correct	25 ms	5560 KB	Output is correct
12	Correct	25 ms	5620 KB	Output is correct
13	Correct	27 ms	5536 KB	Output is correct
14	Correct	26 ms	5568 KB	Output is correct
15	Correct	26 ms	5536 KB	Output is correct
16	Correct	6 ms	1760 KB	Output is correct
17	Correct	8 ms	1832 KB	Output is correct
18	Correct	7 ms	1832 KB	Output is correct
19	Correct	6 ms	1832 KB	Output is correct
20	Correct	6 ms	1820 KB	Output is correct
21	Execution timed out	2062 ms	6696 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	2072 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	30 ms	5556 KB	Output is correct
2	Correct	31 ms	5548 KB	Output is correct
3	Correct	30 ms	5596 KB	Output is correct
4	Correct	26 ms	5596 KB	Output is correct
5	Correct	29 ms	5560 KB	Output is correct
6	Correct	27 ms	5564 KB	Output is correct
7	Correct	31 ms	5652 KB	Output is correct
8	Correct	25 ms	5600 KB	Output is correct
9	Correct	29 ms	5716 KB	Output is correct
10	Correct	25 ms	5620 KB	Output is correct
11	Correct	25 ms	5560 KB	Output is correct
12	Correct	25 ms	5620 KB	Output is correct
13	Correct	27 ms	5536 KB	Output is correct
14	Correct	26 ms	5568 KB	Output is correct
15	Correct	26 ms	5536 KB	Output is correct
16	Correct	6 ms	1760 KB	Output is correct
17	Correct	8 ms	1832 KB	Output is correct
18	Correct	7 ms	1832 KB	Output is correct
19	Correct	6 ms	1832 KB	Output is correct
20	Correct	6 ms	1820 KB	Output is correct
21	Execution timed out	2062 ms	6696 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-