oj.uz

답안 #529520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
529520 2022-02-23T05:58:19 Z zxcvbnm 사다리꼴 (balkan11_trapezoid) C++14
8 / 100
 52 ms 2648 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<array<int, 4>> a(n);
    for(auto& i : a) {
        for(auto& j : i) {
            cin >> j;
        }
    }

    auto cmp = [](const auto& l, const auto& r) {
        return min(l[1], l[3]) < min(r[1], r[3]);
    };

    auto ok = [&](int i, int j) {
        return a[j][0] > a[i][1] && a[j][2] > a[i][3];
    };

    sort(a.begin(), a.end(), cmp);
//    for(auto& i : a) {
//        for(auto& j : i) {
//            cout << j << " ";
//        }
//        cout << "\n";
//    }

//    bool can[n][n];
//    memset(can, false, sizeof can);
//
//    for(int i = 0; i < n; i++) {
//        for(int j = i+1; j < n; j++) {
//            can[i][j] = can[j][i] = ok(i, j);
//        }
//    }

    vector<int> dp(n, 1);
    vector<int> mx(n, 1);
    for(int i = 0; i < n; i++) {
        int l = 0, r = i-1, ans = -1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if (ok(mid, i)) {
                ans = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }

        if (ans == -1) continue;
        dp[i] = dp[i] + mx[ans];
        mx[i] = max(mx[i-1], dp[i]);
    }

    cout << mx[n-1] << " " << mx[n-1] << "\n";
    return 0;
}

Subtask #1
8.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 0 ms 204 KB Partially correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Partially correct 1 ms 332 KB Partially correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 2 ms 332 KB Output isn't correct
7 Incorrect 2 ms 332 KB Output isn't correct
8 Incorrect 2 ms 332 KB Output isn't correct
9 Incorrect 4 ms 460 KB Output isn't correct
10 Partially correct 9 ms 716 KB Partially correct
11 Incorrect 11 ms 844 KB Output isn't correct
12 Incorrect 23 ms 1484 KB Output isn't correct
13 Incorrect 28 ms 1644 KB Output isn't correct
14 Incorrect 36 ms 1924 KB Output isn't correct
15 Incorrect 38 ms 1992 KB Output isn't correct
16 Incorrect 52 ms 2080 KB Output isn't correct
17 Incorrect 39 ms 2244 KB Output isn't correct
18 Partially correct 40 ms 2356 KB Partially correct
19 Incorrect 42 ms 2448 KB Output isn't correct
20 Incorrect 47 ms 2648 KB Output isn't correct