Submission #596938

#	Time	Username	Problem	Language	Result	Execution time	Memory
596938		keta_tsimakuridze	Quality Of Living (IOI10_quality)	C++14	100 / 100	1521 ms	156088 KiB

quality

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#include "quality.h"
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int x[3005][3005], q[3005][3005];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int l = 1, r = R * C , ans = 0;
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) q[i][j] = Q[i - 1][j - 1];
    }
    while(l <= r) {
        int mid = (l + r) / 2;
        int X = 0;
        for(int i = 1; i <= R; i++) {
            for(int j = 1; j <= C; j++) {
                x[i][j] = (q[i][j] <= mid) + x[i - 1][j] - x[i - 1][j - 1] + x[i][j - 1];
                if(i >= H && j >= W) {
                    int sum = x[i][j] + x[i - H][j - W] - x[i - H][j] - x[i][j - W];
                    X = max(X, sum);
                }
            }
        }// cout << "+" << X << endl;
        if(X >= (H * W + 1) / 2) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    return ans;
}

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