Submission #556552

#	Time	Username	Problem	Language	Result	Execution time	Memory
556552		MohamedFaresNebili	Quality Of Living (IOI10_quality)	C++14	100 / 100	2648 ms	175400 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;
        using vi = vector<int>;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound
        /// #define int ll

        const int oo = 1e9 + 7;

        int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
            int res = oo, lo = 1, hi = R * C;
            while(lo <= hi) {
                int md = (lo + hi) / 2; int arr[R][C], dp[R][C]; bool ok = 0;
                for(int l = 0; l < R; l++)
                    for(int i = 0; i < C; i++) {
                        int v = Q[l][i];
                        if(v < md) arr[l][i] = 1;
                        if(v == md) arr[l][i] = 0;
                        if(v > md) arr[l][i] = -1;
                    }
                for(int l = 0; l < R; l++)
                    for(int i = 0; i < C; i++) {
                        dp[l][i] = arr[l][i];
                        if(l) dp[l][i] += dp[l - 1][i];
                        if(i) dp[l][i] += dp[l][i - 1];
                        if(l && i) dp[l][i] -= dp[l - 1][i - 1];
                    }
                for(int l = H - 1; l < R; l++) {
                    for(int i = W - 1; i < C; i++) {
                        int calc = dp[l][i];
                        int lf = l - H, rf = i - W;
                        if(rf >= 0) calc -= dp[l][rf];
                        if(lf >= 0) calc -= dp[lf][i];
                        if(rf >= 0 && lf >= 0)
                            calc += dp[lf][rf];
                        if(calc >= 0) ok = 1;
                    }
                }
                if(ok) res = md, hi = md - 1;
                else lo = md + 1;
            }
            return res;
        }

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