Submission #1176068

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1176068	2025-03-29 20:27:42	VMaksimoski008	Passport (JOI23_passport)	C++17	48 / 100	1297 ms	1114112 KiB

passport

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define ar array
using namespace std;
signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    int n; cin >> n;
    vector<int> L(n+1), R(n+1);
    for(int i=1; i<=n; i++) cin >> L[i] >> R[i];
    vector<ar<int, 3> > G[n+1][n+1];
    int dp[n+1][n+1];
    for(int i=1; i<=n; i++) G[L[i]][R[i]].push_back({ i, i, 1 });
    for(int i=1; i<=n; i++) {
        for(int j=i+1; j<=n; j++) {
            G[i+1][j].push_back({ i, j, 0 });
            G[i][j-1].push_back({ i, j, 0 });
        } 
    }
    for(int i=1; i<=n; i++) {
        int mn = 1e9, mx = 0;
        for(int j=i; j<=n; j++) {
            mn = min(mn, L[j]);
            mx = max(mx, R[j]);
            G[mn][j].push_back({ i, j, 1 });
            G[i][mx].push_back({ i, j, 1 });
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46