Submission #587189

#	Time	Username	Problem	Language	Result	Execution time	Memory
587189		KindaNameless	Quality Of Living (IOI10_quality)	C++14	100 / 100	1701 ms	140328 KiB

quality

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>

#include "quality.h"

using namespace std;

#define ll long long
#define ld long double

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    int l = 0, r = R*C + 1, half = (H*W + 1)/2;
    vector<vector<int>> pref(R, vector<int>(C));
    while(r - l > 1){
        int mid = (l + r) / 2;

        bool exist = 0;
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                pref[i][j] = (Q[i][j] <= mid);
                pref[i][j] += (i == 0 ? 0 : pref[i-1][j]) + (j == 0 ? 0 : pref[i][j-1]) - ((i == 0 || j == 0) ? 0 : pref[i-1][j-1]);
            }
        }

        for(int i = H-1; i < R; ++i){
            for(int j = W-1; j < C; ++j){
                int u = i - H + 1, v = j - W + 1;
                int cnt = pref[i][j] - (u == 0 ? 0 : pref[u-1][j]) - (v == 0 ? 0 : pref[i][v-1]) + ((u == 0 || v == 0) ? 0 : pref[u-1][v-1]);
                if(cnt >= half){
                    exist = 1;
                    break;
                }
            }
            if(exist)break;
        }

        if(exist){
            r = mid;
        }
        else l = mid;
    }
    return r;
}

//int main(){
//    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//    int R, C, H, W; cin >> R >> C >> H >> W;
//
//    vector<vector<int>> Q(R, vector<int>(C));
//
//    for(int i = 0; i < R; ++i){
//        for(int j = 0; j < C; ++j){
//            cin >> Q[i][j];
//        }
//    }
//
//    cout << rectangle(R, C, H, W, Q);
//
//    return 0;
//}

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