oj.uz

답안 #39768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39768 2018-01-18T10:48:25 Z krauch 사다리꼴 (balkan11_trapezoid) C++14
45 / 100
 500 ms 6708 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define sz(a) (int)a.size();
#define all(a) a.begin(), a.end()

const int N = 2e5 + 6, base = 30013;

struct trap {
    int ul, ur, dl, dr;
    trap(){}
} a[N];


int n;
PII d[N];

bool cmp(trap a, trap b) {
    return a.ul < b.ul;
}

int main() {

    cin >> n;
    forn(i, 1, n) {
        cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
    }

    sort(a + 1, a + n + 1, cmp);

    int mx = 0;
    forn(i, 1, n) {
        d[i] = PII(1, 1);
        forn(j, 1, i - 1) {
            if (!(a[j].ur < a[i].ul && a[j].dr < a[i].dl) || d[j].S < d[i].S - 1) continue;
            if (d[j].S > d[i].S - 1) {
                d[i].F = d[j].F;
                d[i].S = d[j].S + 1;
            }
            else d[i].F = (d[j].F + d[i].F) % base;
        }
        mx = max(mx, d[i].S);
    }

    int ans = 0;
    forn(i, 1, n) if (d[i].S == mx) ans = (ans + d[i].F) % base;

    cout << mx << " " << ans << "\n";

    return 0;
}

Subtask #1
45.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6708 KB Output is correct
2 Correct 0 ms 6708 KB Output is correct
3 Correct 1 ms 6708 KB Output is correct
4 Correct 5 ms 6708 KB Output is correct
5 Correct 13 ms 6708 KB Output is correct
6 Correct 26 ms 6708 KB Output is correct
7 Correct 60 ms 6708 KB Output is correct
8 Correct 44 ms 6708 KB Output is correct
9 Correct 212 ms 6708 KB Output is correct
10 Execution timed out 500 ms 6708 KB Execution timed out
11 Execution timed out 500 ms 6708 KB Execution timed out
12 Execution timed out 500 ms 6708 KB Execution timed out
13 Execution timed out 500 ms 6708 KB Execution timed out
14 Execution timed out 500 ms 6708 KB Execution timed out
15 Execution timed out 500 ms 6708 KB Execution timed out
16 Execution timed out 500 ms 6708 KB Execution timed out
17 Execution timed out 500 ms 6708 KB Execution timed out
18 Execution timed out 500 ms 6708 KB Execution timed out
19 Execution timed out 500 ms 6708 KB Execution timed out
20 Execution timed out 500 ms 6708 KB Execution timed out