oj.uz

Submission #660562

# Submission time Handle Problem Language Result Execution time Memory
660562 2022-11-22T09:46:37 Z 600Mihnea trapezoid (balkan11_trapezoid) C++17
45 / 100
 500 ms 2636 KB 
bool home = 0;

#include <bits/stdc++.h>

using namespace std;

const int MODULO = 30013;

struct T
{
  int a;
  int b;
  int c;
  int d;
};

bool operator < (T first, T second)
{
  return first.a < second.a;
}

int main()
{
  if (home == 0)
  {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  }
  else
  {
    freopen ("input.txt", "r", stdin);
  }

  int n;
  cin >> n;
  vector<T> v(n);

  for (auto &it : v)
  {
    cin >> it.a >> it.b >> it.c >> it.d;
  }
  sort(v.begin(), v.end());
  vector<int> dp(n, 0), ways(n, 0);
  for (int i = 0; i < n; i++)
  {
    dp[i] = 1;
    ways[i] = 1;
    for (int j = 0; j < i; j++)
    {
      if (v[j].b < v[i].a && v[j].d < v[i].c)
      {
        if (dp[j] + 1 > dp[i])
        {
          dp[i] = dp[j] + 1;
          ways[i] = ways[j];
        }
        else
        {
          if (dp[j] + 1 == dp[i])
          {
            ways[i] = (ways[i] + ways[j]) % MODULO;
          }
        }
      }
    }
  }
  int mx = *max_element(dp.begin(), dp.end()), cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if (dp[i] == mx)
    {
      cnt = (cnt + ways[i]) % MODULO;
    }
  }
  cout << mx << " " << cnt << "\n";
  return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:30:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 8 ms 340 KB Output is correct
6 Correct 15 ms 392 KB Output is correct
7 Correct 47 ms 396 KB Output is correct
8 Correct 24 ms 340 KB Output is correct
9 Correct 136 ms 468 KB Output is correct
10 Execution timed out 1089 ms 772 KB Time limit exceeded
11 Execution timed out 1070 ms 852 KB Time limit exceeded
12 Execution timed out 1091 ms 1480 KB Time limit exceeded
13 Execution timed out 1079 ms 1648 KB Time limit exceeded
14 Execution timed out 1076 ms 1916 KB Time limit exceeded
15 Execution timed out 1094 ms 1996 KB Time limit exceeded
16 Execution timed out 1084 ms 2132 KB Time limit exceeded
17 Execution timed out 1090 ms 2304 KB Time limit exceeded
18 Execution timed out 1092 ms 2380 KB Time limit exceeded
19 Execution timed out 1095 ms 2508 KB Time limit exceeded
20 Execution timed out 1093 ms 2636 KB Time limit exceeded