oj.uz

Submission #587445

# Submission time Handle Problem Language Result Execution time Memory
587445 2022-07-01T21:35:11 Z Omar_Elgedawy Quality Of Living (IOI10_quality) C++14
100 / 100
 3183 ms 141676 KB 
#include <bits/stdc++.h>
// #include "grader.cpp"
#include "quality.h"
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
int pref[3005][3005];
int sub(int i,int j,int k,int l){
    return pref[k][l]-pref[k][j-1]-pref[i-1][l]+pref[i-1][j-1];
}
int rectangle(int n, int m, int r, int c, int a[3001][3001]) {
    int left=1,right=n*m,ans=1e9;
    vector<pair<int,int>>ch(n*m+1);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ch[a[i][j]]={i,j};
        }
    }
    while(left<=right){
        int mid=(left+right)/2;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if(i&&j)
                    pref[i][j]=a[i-1][j-1]<mid;
                else 
                    pref[i][j]=0;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                pref[i+1][j+1]+=pref[i+1][j];
            }
        }
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++){
                pref[i+1][j+1]+=pref[i][j+1];
            }
        }
        int dec=0;
        for(int i=0;i<=n-r;i++){
            for(int j=0;j<=m-c;j++){
                int num=(ch[mid].F>=i&&ch[mid].F<=(i+r-1)&&ch[mid].S>=j&&ch[mid].S<=(j+c-1));
                int x=sub(i+1,j+1,i+r,j+c);
                if(x>=r*c-x-num){
                    dec=1;
                    if(x==r*c-x-num){
                        ans=min(ans,mid);
                    }
                }
            }
        }
        if(dec)
            right=mid-1;
        else 
            left=mid+1;
    }
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 12 ms 4068 KB Output is correct
8 Correct 12 ms 4052 KB Output is correct
9 Correct 11 ms 3924 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 12 ms 4068 KB Output is correct
8 Correct 12 ms 4052 KB Output is correct
9 Correct 11 ms 3924 KB Output is correct
10 Correct 212 ms 23912 KB Output is correct
11 Correct 148 ms 23892 KB Output is correct
12 Correct 78 ms 16028 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 12 ms 4068 KB Output is correct
8 Correct 12 ms 4052 KB Output is correct
9 Correct 11 ms 3924 KB Output is correct
10 Correct 212 ms 23912 KB Output is correct
11 Correct 148 ms 23892 KB Output is correct
12 Correct 78 ms 16028 KB Output is correct
13 Correct 3183 ms 141676 KB Output is correct
14 Correct 3111 ms 141464 KB Output is correct
15 Correct 2810 ms 134364 KB Output is correct