Submission #521877

#	Time	Username	Problem	Language	Result	Execution time	Memory
521877		antonioqbab	Quality Of Living (IOI10_quality)	C++14	100 / 100	2176 ms	114116 KiB

quality

#include <bits/stdc++.h>

using namespace std;

int rectangle(int N, int M, int y, int x, int q[3001][3001]){
    int left=1, right=N*M;
    while(left<right){
        int m=(left+right)/2;
        auto ok=[&](int cost){
            vector<vector<int>> s(N+1,vector<int>(M+1));
            for(int i = 1; i<=N;++i)
            for(int j=1;j<=M;++j)
                s[i][j]=((q[i-1][j-1]<cost)?-1:(q[i-1][j-1]==cost?0:1))+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            for(int i=1;i<=N-y+1;++i)
            for(int j=1;j<=M-x+1;++j){
                int ii=i+y-1, jj=j+x-1;
                if(s[ii][jj]-s[i-1][jj]-s[ii][j-1]+s[i-1][j-1]<=0)
                    return 1;
            }
            return 0;
        };
        if(ok(m))
            right=m;
        else
            left=m+1;
    }
    return left;
}

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