Submission #2544550


Source Code Expand

#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int n;
const int INF = 1e9;

struct line {
	int h;
	int w;

	bool operator< (const line &o) const {
		return h < o.h;
	}
};
vector <line> xy, yx;

int solve (vector <line> &line) {
	vector <int> dp(n, INF);
	rep (i, n) {
		*lower_bound(dp.begin(), dp.end(), line[i].w) = line[i].w;
	}
	return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}


int main() {
	cin >> n;
	xy = yx = vector <line> (n);
	rep (i, n) {
		int h, w;
		cin >> w >> h;
		xy[i].h = h; xy[i].w = w;
		yx[i].w = h; yx[i].h = w;
	}
	sort(xy.begin(), xy.end());
	sort(yx.begin(), yx.end());

	cout << max(solve(xy), solve(yx)) << endl;

	return 0;
}

Submission Info

Submission Time
Task D - プレゼント
User Masumi
Language C++14 (GCC 5.4.1)
Score 30
Code Size 798 Byte
Status WA
Exec Time 96 ms
Memory 2176 KB

Judge Result

Set Name Sample Subtask0 All
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 4
AC × 19
AC × 23
WA × 11
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask0 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
All sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 1 ms 256 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB
subtask0_0.txt AC 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_10.txt AC 2 ms 256 KB
subtask0_11.txt AC 2 ms 256 KB
subtask0_12.txt AC 2 ms 256 KB
subtask0_13.txt AC 2 ms 256 KB
subtask0_14.txt AC 2 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask0_3.txt AC 1 ms 256 KB
subtask0_4.txt AC 2 ms 256 KB
subtask0_5.txt AC 1 ms 256 KB
subtask0_6.txt AC 2 ms 256 KB
subtask0_7.txt AC 2 ms 256 KB
subtask0_8.txt AC 2 ms 256 KB
subtask0_9.txt AC 1 ms 256 KB
subtask1_0.txt WA 57 ms 1424 KB
subtask1_1.txt AC 3 ms 256 KB
subtask1_10.txt AC 83 ms 2176 KB
subtask1_11.txt AC 79 ms 2176 KB
subtask1_12.txt WA 95 ms 2176 KB
subtask1_13.txt WA 93 ms 2176 KB
subtask1_14.txt WA 95 ms 2176 KB
subtask1_2.txt WA 16 ms 512 KB
subtask1_3.txt WA 80 ms 1920 KB
subtask1_4.txt WA 96 ms 2176 KB
subtask1_5.txt WA 14 ms 512 KB
subtask1_6.txt WA 70 ms 1756 KB
subtask1_7.txt WA 38 ms 1024 KB
subtask1_8.txt AC 81 ms 1968 KB
subtask1_9.txt WA 41 ms 1152 KB