oj.uz

Submission #243815

# Submission time Handle Problem Language Result Execution time Memory
243815 2020-07-01T21:02:16 Z ctziapo Quality Of Living (IOI10_quality) C++14
100 / 100
 3083 ms 142348 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 30 ms 3072 KB Output is correct
8 Correct 32 ms 3072 KB Output is correct
9 Correct 27 ms 2944 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 30 ms 3072 KB Output is correct
8 Correct 32 ms 3072 KB Output is correct
9 Correct 27 ms 2944 KB Output is correct
10 Correct 326 ms 23044 KB Output is correct
11 Correct 326 ms 22904 KB Output is correct
12 Correct 173 ms 13560 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 30 ms 3072 KB Output is correct
8 Correct 32 ms 3072 KB Output is correct
9 Correct 27 ms 2944 KB Output is correct
10 Correct 326 ms 23044 KB Output is correct
11 Correct 326 ms 22904 KB Output is correct
12 Correct 173 ms 13560 KB Output is correct
13 Correct 3083 ms 142348 KB Output is correct
14 Correct 3069 ms 142328 KB Output is correct
15 Correct 2809 ms 130100 KB Output is correct