oj.uz

답안 #1092505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1092505 2024-09-24T08:41:44 Z NguyenPhucThang 사다리꼴 (balkan11_trapezoid) C++14
0 / 100
 500 ms 1560 KB 
#include <bits/stdc++.h>
#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vii vector<pii>
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

using namespace std;
const int base = 31;
const ll mod = 30013;
const ll oo = 1e18;
const int N = 1e6 + 5;

ll dp[N], cnt[N];
struct trapezoid{
	int a, b, c, d;

	bool operator < (const trapezoid &other){
		return min(a, c) < min(other.a, other.c);
	}
} trape[N];


int main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
#ifndef ONLINE_JUDGE
   freopen(file".inp", "r", stdin);
   freopen(file".out", "w", stdout);
#endif
	int n;
	cin >> n;
	forr(i, 1, n) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		trape[i] = {a, b, c, d};
	}

	sort(trape + 1, trape + n + 1);

	forr(i, 1, n) cnt[i] = 1;

	forr(i, 1, n){
		dp[i] = 1;
		forr(j, 1, i - 1){
			if (trape[j].b < trape[i].a && trape[j].d < trape[i].c){
				if (dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
					cnt[i] = cnt[j];
				}
				else if (dp[j] + 1 == dp[i]){
					cnt[i] += cnt[j];
					cnt[i] %= mod;
				}
			}
		}
	}

	int res1 = 0, res2;
	forr(i, 1, n){
		if (res1 < dp[i]) res1 = dp[i], res2 = cnt[i];
	}
	cout << res1 << " " << res2;
   return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:41:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |    freopen(file".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:42:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |    freopen(file".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:76:25: warning: 'res2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |  cout << res1 << " " << res2;
      |                         ^~~~

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 633 ms 1372 KB Time limit exceeded
2 Execution timed out 619 ms 1360 KB Time limit exceeded
3 Execution timed out 594 ms 1360 KB Time limit exceeded
4 Execution timed out 618 ms 1344 KB Time limit exceeded
5 Execution timed out 599 ms 1360 KB Time limit exceeded
6 Execution timed out 597 ms 1380 KB Time limit exceeded
7 Execution timed out 596 ms 1480 KB Time limit exceeded
8 Execution timed out 605 ms 1360 KB Time limit exceeded
9 Execution timed out 599 ms 1364 KB Time limit exceeded
10 Execution timed out 597 ms 1368 KB Time limit exceeded
11 Execution timed out 640 ms 1372 KB Time limit exceeded
12 Execution timed out 617 ms 1560 KB Time limit exceeded
13 Execution timed out 612 ms 1368 KB Time limit exceeded
14 Execution timed out 597 ms 1372 KB Time limit exceeded
15 Execution timed out 600 ms 1372 KB Time limit exceeded
16 Execution timed out 600 ms 1364 KB Time limit exceeded
17 Execution timed out 641 ms 1360 KB Time limit exceeded
18 Execution timed out 601 ms 1388 KB Time limit exceeded
19 Execution timed out 618 ms 1488 KB Time limit exceeded
20 Execution timed out 601 ms 1488 KB Time limit exceeded