oj.uz

Submission #39768

# Submission time Handle Problem Language Result Execution time Memory
39768 2018-01-18T10:48:25 Z krauch trapezoid (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

# Verdict Execution time Memory 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