oj.uz

Submission #433890

# Submission time Handle Problem Language Result Execution time Memory
433890 2021-06-20T11:53:10 Z oscar1f Boat (APIO16_boat) C++17
9 / 100
 2000 ms 524292 KB 
#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;
    }
    if (maxMaint<mini[idEcole]) {
        return memo[(long long)idEcole*(long long)INFINI+(long long)maxMaint]=(dyna(idEcole+1,maxMaint)+dyna(idEcole,mini[idEcole]))%INFINI;
    }
    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 31 ms 5592 KB Output is correct
2 Correct 31 ms 5644 KB Output is correct
3 Correct 25 ms 5556 KB Output is correct
4 Correct 23 ms 5568 KB Output is correct
5 Correct 24 ms 5672 KB Output is correct
6 Correct 29 ms 5588 KB Output is correct
7 Correct 25 ms 5592 KB Output is correct
8 Correct 25 ms 5568 KB Output is correct
9 Correct 33 ms 5592 KB Output is correct
10 Correct 34 ms 5584 KB Output is correct
11 Correct 26 ms 5556 KB Output is correct
12 Correct 26 ms 5664 KB Output is correct
13 Correct 25 ms 5548 KB Output is correct
14 Correct 26 ms 5552 KB Output is correct
15 Correct 25 ms 5564 KB Output is correct
16 Correct 7 ms 1704 KB Output is correct
17 Correct 7 ms 1832 KB Output is correct
18 Correct 7 ms 1764 KB Output is correct
19 Correct 7 ms 1832 KB Output is correct
20 Correct 6 ms 1704 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5592 KB Output is correct
2 Correct 31 ms 5644 KB Output is correct
3 Correct 25 ms 5556 KB Output is correct
4 Correct 23 ms 5568 KB Output is correct
5 Correct 24 ms 5672 KB Output is correct
6 Correct 29 ms 5588 KB Output is correct
7 Correct 25 ms 5592 KB Output is correct
8 Correct 25 ms 5568 KB Output is correct
9 Correct 33 ms 5592 KB Output is correct
10 Correct 34 ms 5584 KB Output is correct
11 Correct 26 ms 5556 KB Output is correct
12 Correct 26 ms 5664 KB Output is correct
13 Correct 25 ms 5548 KB Output is correct
14 Correct 26 ms 5552 KB Output is correct
15 Correct 25 ms 5564 KB Output is correct
16 Correct 7 ms 1704 KB Output is correct
17 Correct 7 ms 1832 KB Output is correct
18 Correct 7 ms 1764 KB Output is correct
19 Correct 7 ms 1832 KB Output is correct
20 Correct 6 ms 1704 KB Output is correct
21 Correct 370 ms 103964 KB Output is correct
22 Correct 360 ms 103972 KB Output is correct
23 Correct 359 ms 104236 KB Output is correct
24 Correct 401 ms 104224 KB Output is correct
25 Correct 363 ms 104948 KB Output is correct
26 Correct 332 ms 80216 KB Output is correct
27 Correct 313 ms 80176 KB Output is correct
28 Correct 307 ms 80108 KB Output is correct
29 Correct 310 ms 80136 KB Output is correct
30 Execution timed out 2080 ms 474440 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 535 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 31 ms 5592 KB Output is correct
2 Correct 31 ms 5644 KB Output is correct
3 Correct 25 ms 5556 KB Output is correct
4 Correct 23 ms 5568 KB Output is correct
5 Correct 24 ms 5672 KB Output is correct
6 Correct 29 ms 5588 KB Output is correct
7 Correct 25 ms 5592 KB Output is correct
8 Correct 25 ms 5568 KB Output is correct
9 Correct 33 ms 5592 KB Output is correct
10 Correct 34 ms 5584 KB Output is correct
11 Correct 26 ms 5556 KB Output is correct
12 Correct 26 ms 5664 KB Output is correct
13 Correct 25 ms 5548 KB Output is correct
14 Correct 26 ms 5552 KB Output is correct
15 Correct 25 ms 5564 KB Output is correct
16 Correct 7 ms 1704 KB Output is correct
17 Correct 7 ms 1832 KB Output is correct
18 Correct 7 ms 1764 KB Output is correct
19 Correct 7 ms 1832 KB Output is correct
20 Correct 6 ms 1704 KB Output is correct
21 Correct 370 ms 103964 KB Output is correct
22 Correct 360 ms 103972 KB Output is correct
23 Correct 359 ms 104236 KB Output is correct
24 Correct 401 ms 104224 KB Output is correct
25 Correct 363 ms 104948 KB Output is correct
26 Correct 332 ms 80216 KB Output is correct
27 Correct 313 ms 80176 KB Output is correct
28 Correct 307 ms 80108 KB Output is correct
29 Correct 310 ms 80136 KB Output is correct
30 Execution timed out 2080 ms 474440 KB Time limit exceeded
31 Halted 0 ms 0 KB -