oj.uz

Submission #766894

# Submission time Handle Problem Language Result Execution time Memory
766894 2023-06-26T08:38:44 Z irmuun Quality Of Living (IOI10_quality) C++17
100 / 100
 1334 ms 140156 KB 
#include<bits/stdc++.h>
#include "quality.h"
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

int rectangle(int R,int C,int H,int W,int Q[3001][3001]){
    int sum[R+1][C+1],m=H*W/2+1;
    int l=1,r=R*C;
    while(l<r){
        int mid=(l+r)/2;
        bool ok=false;
        sum[0][0]=0;
        for(int i=0;i<=R;i++){
            for(int j=0;j<=C;j++){
                if(i==0||j==0){
                    sum[i][j]=0;
                    continue;
                }
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(Q[i-1][j-1]<=mid);
                if(i>=H&&j>=W){
                    if(sum[i][j]-sum[i-H][j]-sum[i][j-W]+sum[i-H][j-W]>=m){
                        ok=true;
                    }
                }
            }
        }
        if(ok==true){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    return l;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 14 ms 2652 KB Output is correct
8 Correct 11 ms 2732 KB Output is correct
9 Correct 11 ms 2516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 14 ms 2652 KB Output is correct
8 Correct 11 ms 2732 KB Output is correct
9 Correct 11 ms 2516 KB Output is correct
10 Correct 140 ms 18828 KB Output is correct
11 Correct 137 ms 18868 KB Output is correct
12 Correct 68 ms 11492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 14 ms 2652 KB Output is correct
8 Correct 11 ms 2732 KB Output is correct
9 Correct 11 ms 2516 KB Output is correct
10 Correct 140 ms 18828 KB Output is correct
11 Correct 137 ms 18868 KB Output is correct
12 Correct 68 ms 11492 KB Output is correct
13 Correct 1334 ms 140156 KB Output is correct
14 Correct 1330 ms 140152 KB Output is correct
15 Correct 1208 ms 129460 KB Output is correct