oj.uz

Submission #908508

# Submission time Handle Problem Language Result Execution time Memory
908508 2024-01-16T13:12:04 Z duckindog trapezoid (balkan11_trapezoid) C++14
40 / 100
 38 ms 788 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) {
          d[i] = d[j] + 1;
          f[i] = 0;
        }

        if (d[i] == d[j] + 1) {
          f[i] = (f[i] + f[j]) % M;
        }

      }
    }
  }

  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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 540 KB Output is correct
7 Correct 33 ms 788 KB Output is correct
8 Correct 38 ms 348 KB Output is 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 604 KB Execution killed with signal 11
13 Runtime error 2 ms 604 KB Execution killed with signal 11
14 Runtime error 2 ms 600 KB Execution killed with signal 11
15 Runtime error 2 ms 604 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 2 ms 604 KB Execution killed with signal 11
19 Runtime error 2 ms 604 KB Execution killed with signal 11
20 Runtime error 2 ms 604 KB Execution killed with signal 11