답안 #793827

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-