oj.uz

Submission #587441

# Submission time Handle Problem Language Result Execution time Memory
587441 2022-07-01T21:27:02 Z Omar_Elgedawy Quality Of Living (IOI10_quality) C++14
80 / 100
 4987 ms 262144 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;
    map<int,pair<int,int>>ch;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;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 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 5 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 4 ms 1748 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 5 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 67 ms 8996 KB Output is correct
8 Correct 44 ms 8996 KB Output is correct
9 Correct 54 ms 8396 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 5 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 67 ms 8996 KB Output is correct
8 Correct 44 ms 8996 KB Output is correct
9 Correct 54 ms 8396 KB Output is correct
10 Correct 1438 ms 78848 KB Output is correct
11 Correct 1203 ms 78888 KB Output is correct
12 Correct 659 ms 43436 KB Output is correct

Subtask #5
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 5 ms 1748 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 4 ms 1748 KB Output is correct
7 Correct 67 ms 8996 KB Output is correct
8 Correct 44 ms 8996 KB Output is correct
9 Correct 54 ms 8396 KB Output is correct
10 Correct 1438 ms 78848 KB Output is correct
11 Correct 1203 ms 78888 KB Output is correct
12 Correct 659 ms 43436 KB Output is correct
13 Runtime error 4987 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -