oj.uz

Submission #965416

# Submission time Handle Problem Language Result Execution time Memory
965416 2024-04-18T13:13:00 Z hirayuu_oj Quality Of Living (IOI10_quality) C++17
100 / 100
 1744 ms 140412 KB 
#include "quality.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) x.begin(),x.end();
using ll=long long;
const ll INF=1LL<<60;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    vector<vector<int>> cum(R+1,vector<int>(C+1,0));
    int ok=R*C,ng=0;
    while(ok-ng>1){
        int mid=(ok+ng)/2;
        rep(i,R+1){
            cum[i][0]=0;
        }
        rep(i,C+1){
            cum[0][i]=0;
        }
        rep(i,R){
            rep(j,C){
                cum[i+1][j+1]=cum[i+1][j]+cum[i][j+1]-cum[i][j];
                if(Q[i][j]<=mid)cum[i+1][j+1]++;
            }
        }
        bool can=false;
        rep(i,R-H+1){
            rep(j,C-W+1){
                int val=cum[i+H][j+W]-cum[i+H][j]-cum[i][j+W]+cum[i][j];
                if(val>=H*W-val)can=true;
            }
        }
        if(can)ok=mid;
        else ng=mid;
    }
    return ok;
}
//g++ -o quality -O2 quality.cpp grader.cpp

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2468 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 14 ms 5464 KB Output is correct
8 Correct 14 ms 5468 KB Output is correct
9 Correct 13 ms 5340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2468 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 14 ms 5464 KB Output is correct
8 Correct 14 ms 5468 KB Output is correct
9 Correct 13 ms 5340 KB Output is correct
10 Correct 176 ms 23380 KB Output is correct
11 Correct 170 ms 23588 KB Output is correct
12 Correct 85 ms 18000 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2468 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 14 ms 5464 KB Output is correct
8 Correct 14 ms 5468 KB Output is correct
9 Correct 13 ms 5340 KB Output is correct
10 Correct 176 ms 23380 KB Output is correct
11 Correct 170 ms 23588 KB Output is correct
12 Correct 85 ms 18000 KB Output is correct
13 Correct 1744 ms 140412 KB Output is correct
14 Correct 1689 ms 140408 KB Output is correct
15 Correct 1584 ms 130044 KB Output is correct