oj.uz

Submission #688459

# Submission time Handle Problem Language Result Execution time Memory
688459 2023-01-27T13:23:31 Z Khizri Quality Of Living (IOI10_quality) C++17
100 / 100
 1503 ms 175380 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=3e3+5;
int arr[mxn][mxn],dp[mxn][mxn];
int query(int i,int j,int x,int y){
    return dp[i][j]-dp[i-x][j]-dp[i][j-y]+dp[i-x][j-y];
}
int rectangle(int n, int m, int x, int y, int Q[3001][3001]) {
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            arr[i][j]=Q[i-1][j-1];
        }
    }
    int l=1,r=n*m;
    while(l<=r){
        int mm=(l+r)/2;
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(arr[i][j]<=mm){
                    dp[i][j]=1;
                }
                else if(arr[i][j]>mm){
                    dp[i][j]=0;
                }
                dp[i][j]+=dp[i-1][j];
                dp[i][j]+=dp[i][j-1];
                dp[i][j]-=dp[i-1][j-1];
                if(i>=x&&j>=y){
                    if(query(i,j,x,y)>=(x*y+1)/2){
                        ans=1;
                    }
                }
            }
        }
        if(ans){
            r=mm-1;
        }
        else{
            l=mm+1;
        }
    }
    return r+1;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 14 ms 5504 KB Output is correct
8 Correct 14 ms 5460 KB Output is correct
9 Correct 14 ms 5252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 14 ms 5504 KB Output is correct
8 Correct 14 ms 5460 KB Output is correct
9 Correct 14 ms 5252 KB Output is correct
10 Correct 163 ms 30752 KB Output is correct
11 Correct 166 ms 30792 KB Output is correct
12 Correct 88 ms 21452 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 2 ms 1620 KB Output is correct
7 Correct 14 ms 5504 KB Output is correct
8 Correct 14 ms 5460 KB Output is correct
9 Correct 14 ms 5252 KB Output is correct
10 Correct 163 ms 30752 KB Output is correct
11 Correct 166 ms 30792 KB Output is correct
12 Correct 88 ms 21452 KB Output is correct
13 Correct 1503 ms 175380 KB Output is correct
14 Correct 1463 ms 175372 KB Output is correct
15 Correct 1372 ms 168304 KB Output is correct