Submission #1176228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176228		lnwrice	삶의 질 (IOI10_quality)	C++20	40 / 100	5090 ms	3144 KiB

quality

#include "quality.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	const int n = R, m = C, h = H, w = W;
	const int MAX = 9000012, MAX_INT = 2000000024;
	int i, j, k, l;
	int t = (h*w)/2, min_ = MAX_INT, c;

	set<int> arr;
	for(k = 0; k < h; k++) {
		for(l = 0; l < w; l++) {
			arr.insert(Q[k][l]);
		}
	}
	c = *next(arr.begin(), t);
	if(c < min_) min_ = c;
	
	for(i = 0; i <= n - h; ) {
        //cout << i << endl;
		for(j = 0; j < m - w; j++) {
			for(k = i; k < i + h; k++) {
				auto it = lower_bound(arr.begin(), arr.end(), Q[k][j]);
				/*/*
				for(auto it : arr) {
					cout << it << " ";
				}
				cout << endl;

				cout << "target : " << Q[k][j] << endl;
				cout << "erase : " << *it << endl;
				cout << "insert : " << k << ", " << j+w << endl;
				/**/
				arr.erase(it);
				arr.insert(Q[k][j+w]);
			}
			c = *next(arr.begin(), t);
			if(c < min_) min_ = c;
		}

        i++;
        if(i > n-h) continue;
        for(k = 0; k < w; k++) {
            auto it = lower_bound(arr.begin(), arr.end(), Q[i-1][j+k]);
            /*/*
            for(auto it : arr) {
                cout << it << " ";
            }
            cout << endl;

            cout << "target : " << Q[i-1][j+k] << endl;
            cout << "erase : " << *it << endl;
            cout << "insert : " << i+h-1 << ", " << j+k << endl;
            /**/
            arr.erase(it);
            arr.insert(Q[i+h-1][j+k]);
        }
        c = *next(arr.begin(), t);
        if(c < min_) min_ = c;

		for(j -= 1; j >= 0; j--) {
			for(k = i; k < i + h; k++) {
				auto it = lower_bound(arr.begin(), arr.end(), Q[k][j+w]);
				/*/*
				for(auto it : arr) {
					cout << it << " ";
				}
				cout << endl;

				cout << "target : " << Q[k][j+w] << endl;
				cout << "erase : " << *it << endl;
				cout << "insert : " << k << ", " << j << endl;
				/**/
				arr.erase(it);
				arr.insert(Q[k][j]);
			}
			c = *next(arr.begin(), t);
			if(c < min_) min_ = c;
		}

        i++;
        if(i > n-h) continue;
        for(k = 0; k < w; k++) {
            auto it = lower_bound(arr.begin(), arr.end(), Q[i-1][k]);
            /*/*
            for(auto it : arr) {
                cout << it << " ";
            }
            cout << endl;

            cout << "target : " << Q[i-1][k] << endl;
            cout << "erase : " << *it << endl;
            cout << "insert : " << i+h-1 << ", " << k << endl;
            /**/
            arr.erase(it);
            arr.insert(Q[i+h-1][k]);
        }
        c = *next(arr.begin(), t);
        if(c < min_) min_ = c;
	}
	
	return min_;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20