Submission #243815

#	Time	Username	Problem	Language	Result	Execution time	Memory
243815		ctziapo	Quality Of Living (IOI10_quality)	C++14	100 / 100	3083 ms	142348 KiB

quality

#include <stdio.h>
#include <stdlib.h>
#include "quality.h"
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;


int rectangle(int R, int C, int H, int W, int a[3001][3001]) {

    int n=R;
    int m=C;
    int h=H;
    int w=W;
    int ans=n*m;
    int l=1;
    int r=n*m;

    while(l<=r){

        int mid=(l+r)/2;
//        p(mid);
        int f[n+3][m+3]={};

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(a[i][j]<mid){
                    f[i+1][j+1]=-1;
                }
                else
                    if(a[i][j]>mid)
                        f[i+1][j+1]=1;
                else
                    f[i+1][j+1]=0;
            }
        }

        int pr[n+2][m+2]={};

        for(int i=1;i<=n;i++){
            int p2=0;
            for(int j=1;j<=m;j++){
                p2+=f[i][j];

                if(i!=0){
                    pr[i][j]=pr[i-1][j]+p2;
                }
                else
                    pr[i][j]=p2;
            }
        }
        /*
        cout<<"f"<<endl;
        cout<<endl;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<f[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;

         cout<<endl;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cout<<pr[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
//        p(mid);
*/
        int zero=0;
        int neg=0;
        int pos=0;
        for(int i=h;i<=n;i++){
            for(int j=w;j<=m;j++){
                int p=pr[i][j] - pr[i-h][j] - pr[i][j-w] + pr[i-h][j-w];
               // cout<<"dd "<<pr[i][j] - pr[i-h][j] - pr[i][j-w] + pr[i-h][j-w]<<endl;
               // cout<<"dd2 "<<i<<" "<<j <<" "<<i-h+1<<" "<<j-w+1 <<endl;
                if(p>0)
                    pos=1;
                if(p<0)
                    neg=1;
                if(p==0)
                    zero=1;
            }
        }
        if(zero==1){
            ans=min(ans,mid);
        }

        if(neg==1){
            r=mid-1;
        }
        else
            l=mid+1;
    }

//    p(ans);
	return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:77:13: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
         int pos=0;
             ^~~

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