Submission #660561

#	Time	Username	Problem	Language	Result	Execution time	Memory
660561		600Mihnea	trapezoid (balkan11_trapezoid)	C++17	50 / 100	1076 ms	5320 KiB

trapezoid

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.b < second.b;
}

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 (stderr)

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: 50 / 100