oj.uz

Submission #587444

# Submission time Handle Problem Language Result Execution time Memory
587444 2022-07-01T21:31:05 Z Omar_Elgedawy Quality Of Living (IOI10_quality) C++14
80 / 100
 4689 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<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 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 1744 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 7 ms 1704 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 1744 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 7 ms 1704 KB Output is correct
7 Correct 68 ms 8996 KB Output is correct
8 Correct 46 ms 9016 KB Output is correct
9 Correct 54 ms 8424 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 1744 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 7 ms 1704 KB Output is correct
7 Correct 68 ms 8996 KB Output is correct
8 Correct 46 ms 9016 KB Output is correct
9 Correct 54 ms 8424 KB Output is correct
10 Correct 1426 ms 78772 KB Output is correct
11 Correct 1186 ms 78860 KB Output is correct
12 Correct 647 ms 43508 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 1744 KB Output is correct
5 Correct 6 ms 1748 KB Output is correct
6 Correct 7 ms 1704 KB Output is correct
7 Correct 68 ms 8996 KB Output is correct
8 Correct 46 ms 9016 KB Output is correct
9 Correct 54 ms 8424 KB Output is correct
10 Correct 1426 ms 78772 KB Output is correct
11 Correct 1186 ms 78860 KB Output is correct
12 Correct 647 ms 43508 KB Output is correct
13 Runtime error 4689 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -