oj.uz

Submission #587438

# Submission time Handle Problem Language Result Execution time Memory
587438 2022-07-01T21:24:59 Z Omar_Elgedawy Quality Of Living (IOI10_quality) C++14
80 / 100
 4686 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[3002][3002];
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 i=0;i<=n;i++){
        //     for(int j=0;j<=m;j++){
        //         cout<<pref[i][j]<<' ';
        //     }cout<<el;
        // }cout<<el;
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++){
                pref[i+1][j+1]+=pref[i][j+1];
            }
        }
        // for(int i=0;i<=n;i++){
        //     for(int j=0;j<=m;j++){
        //         cout<<pref[i][j]<<' ';
        //     }cout<<el;
        // }cout<<el;
        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){
                        // cout<<i<<' '<<j<<' '<<i+r-1<<' '<<j+c-1<<' '<<x<<' '<<mid<<el<<el;
                        ans=min(ans,mid);
                    }
                }
            }
        }
        // cout<<dec<<el;
        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 1708 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 6 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 1708 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 6 ms 1748 KB Output is correct
7 Correct 70 ms 8968 KB Output is correct
8 Correct 43 ms 9004 KB Output is correct
9 Correct 56 ms 8448 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 1708 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 6 ms 1748 KB Output is correct
7 Correct 70 ms 8968 KB Output is correct
8 Correct 43 ms 9004 KB Output is correct
9 Correct 56 ms 8448 KB Output is correct
10 Correct 1366 ms 78760 KB Output is correct
11 Correct 1178 ms 80444 KB Output is correct
12 Correct 673 ms 45280 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 1708 KB Output is correct
5 Correct 8 ms 1748 KB Output is correct
6 Correct 6 ms 1748 KB Output is correct
7 Correct 70 ms 8968 KB Output is correct
8 Correct 43 ms 9004 KB Output is correct
9 Correct 56 ms 8448 KB Output is correct
10 Correct 1366 ms 78760 KB Output is correct
11 Correct 1178 ms 80444 KB Output is correct
12 Correct 673 ms 45280 KB Output is correct
13 Runtime error 4686 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -