Submission #793827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
793827	2023-07-26T07:06:43 Z	vjudge1	Passport (JOI23_passport)	C++17	16 / 100	2000 ms	2652 KB

passport

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3010;
const int INF = 1e9;

int dp[N][N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    int L[n + 1], R[n + 1];
    for(int i = 1; i <= n; i++)
        cin >> L[i] >> R[i];
    int mx[n + 1] = {};
    for(int i = 1; i <= n; i++) 
        mx[i] = max(mx[i - 1], R[i]);
    if(n <= 300) {
        dp[1][n] = 0;
        for(int len = n - 1; len >= 1; len--) {
            for(int l = 1; l <= n - len + 1; l++) {
                int r = l + len - 1;
                dp[l][r] = INF;
                for(int i = l; i <= r; i++) {
                    dp[l][r] = min(dp[l][r], dp[min(l, L[i])][max(r, R[i])] + 1);
                } 
            }
        }   
        int q;
        cin >> q;
        while(q--) {
            int x;
            cin >> x;
            cout << (dp[x][x] == INF ? -1 : dp[x][x]) << '\n';
        }
        return 0;
    }
    int q;
    cin >> q;
    int x, res = 0;
    cin >> x;
    while(x < n) {
        res++;
        x = max(x, mx[x]);
    }
    cout << res;
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	25 ms	2504 KB	Output is correct
5	Correct	25 ms	2508 KB	Output is correct
6	Correct	25 ms	2652 KB	Output is correct
7	Correct	21 ms	2488 KB	Output is correct
8	Execution timed out	2080 ms	2144 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	11 ms	1620 KB	Output is correct
12	Correct	15 ms	1592 KB	Output is correct
13	Correct	13 ms	1620 KB	Output is correct
14	Correct	13 ms	1548 KB	Output is correct
15	Correct	15 ms	1684 KB	Output is correct

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	11 ms	1620 KB	Output is correct
12	Correct	15 ms	1592 KB	Output is correct
13	Correct	13 ms	1620 KB	Output is correct
14	Correct	13 ms	1548 KB	Output is correct
15	Correct	15 ms	1684 KB	Output is correct
16	Incorrect	1 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	11 ms	1620 KB	Output is correct
12	Correct	15 ms	1592 KB	Output is correct
13	Correct	13 ms	1620 KB	Output is correct
14	Correct	13 ms	1548 KB	Output is correct
15	Correct	15 ms	1684 KB	Output is correct
16	Incorrect	1 ms	340 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 46.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	25 ms	2504 KB	Output is correct
5	Correct	25 ms	2508 KB	Output is correct
6	Correct	25 ms	2652 KB	Output is correct
7	Correct	21 ms	2488 KB	Output is correct
8	Execution timed out	2080 ms	2144 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-