oj.uz

Submission #908506

# Submission time Handle Problem Language Result Execution time Memory
908506 2024-01-16T13:10:13 Z duckindog trapezoid (balkan11_trapezoid) C++14
28 / 100
 36 ms 628 KB 
// from duckindog wth depression
#include<bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10,
          M = 30013;
struct rec {
  int a = 0, b = 0, c = 0, d = 0;

  bool operator < (const rec& rhs) {
    return make_pair(min(a, c), min(b, d)) < make_pair(min(rhs.a, rhs.c), min(rhs.b, rhs.d));
  }
} r[N];
int n;
int d[N], f[N];
bool crossed(rec x, rec y) {
  if (min(x.a, x.c) > min(y.a, y.c)) swap(x, y);
  return (x.b >= y.a || x.d >= y.c);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);

  if (fopen("duck.inp", "r")) {
    freopen("duck.inp", "r", stdin);
    freopen("duck.out", "w", stdout);
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    r[i] = {a, b, c, d};
  }
  sort(r + 1, r + n + 1);

  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (!crossed(r[i], r[j])) {
        if (d[i] == d[j] + 1) f[i] = (f[i] + f[j]) % M;
        else f[i] = f[j];
        d[i] = max(d[i], d[j] + 1);
      }
    }
  }

  int ma = *max_element(d + 1, d + n + 1);
  int cnt = 0;
  for (int i = 1; i <= n; ++i) if (d[i] == ma) cnt = (cnt + f[i]) % M;
  cout << ma << ' ' << cnt << '\n';

}

Compilation message

trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen("duck.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("duck.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Partially correct 2 ms 556 KB Partially correct
4 Correct 4 ms 348 KB Output is correct
5 Partially correct 7 ms 348 KB Partially correct
6 Partially correct 14 ms 524 KB Partially correct
7 Correct 35 ms 348 KB Output is correct
8 Partially correct 36 ms 564 KB Partially correct
9 Runtime error 2 ms 600 KB Execution killed with signal 11
10 Runtime error 2 ms 604 KB Execution killed with signal 11
11 Runtime error 2 ms 604 KB Execution killed with signal 11
12 Runtime error 2 ms 628 KB Execution killed with signal 11
13 Runtime error 2 ms 604 KB Execution killed with signal 11
14 Runtime error 4 ms 604 KB Execution killed with signal 11
15 Runtime error 3 ms 600 KB Execution killed with signal 11
16 Runtime error 2 ms 604 KB Execution killed with signal 11
17 Runtime error 2 ms 604 KB Execution killed with signal 11
18 Runtime error 3 ms 604 KB Execution killed with signal 11
19 Runtime error 2 ms 532 KB Execution killed with signal 11
20 Runtime error 2 ms 604 KB Execution killed with signal 11