정올 _ 1219. 모자이크

 

 

 

 

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

void quick_sort(int right, int left, int list[][2]) {
	if (right <= left)
		return;
	int R = right, L = left;
	int middle = (R + L) / 2;
	while (R >= L) {
		while (list[R][1] >= list[middle][1]&&R>=middle) R--;
		while (list[L][1] <= list[middle][1]&&L<=middle) L++;
		//swap할 것을 찾는다. 
		if (R > L) {
			int temp[2] = { list[R][0],list[R][1] };
			list[R][0] = list[L][0];
			list[R][1] = list[L][1];
			list[L][0] = temp[0];
			list[L][1] = temp[1];
		}
		else if (R == L) {
			int temp[2] = { list[middle][0],list[middle][1] };
			list[middle][0] = list[L][0];
			list[middle][1] = list[L][1];
			list[L][0] = temp[0];
			list[L][1] = temp[1];
		}
		else {
			if(middle+1<right)
				quick_sort(right, middle+1, list);
			if(middle-1>left)
				quick_sort(middle-1, left, list);
		}
	}
}

int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	int column, row;
	cin >> column >> row;
	int have_paper;
	cin >> have_paper;
	int tail;
	cin >> tail;
	int tail_list[1010][2] = { 0 };
	int max_column = 0;
	for (int i = 1; i <= tail; i++) {
		cin >> tail_list[i][0] >> tail_list[i][1];
		if (max_column < tail_list[i][0])
			max_column = tail_list[i][0];
	}
	quick_sort( tail,1, tail_list);
	while (1) {
		int paper_amount = 0;
		int s = 0;
		for (int i = 1; i <= tail; i++) {
			if (paper_amount > have_paper) {
				s = 1;
				break;
			}
			int c=max_column, r=tail_list[i][1]+max_column;
			paper_amount++;
			for (;i<=tail; i++) {
				if (tail_list[i][0] > c || tail_list[i][1] > r) {
					i -= 1;
					break;
				}
			}
		}
		if (s == 1) {
			max_column++;
		}
		else {
			cout << max_column;
			break;
		}
	}
	return 0;
}