oj.uz

답안 #775757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775757 2023-07-06T21:43:45 Z DobromirAngelov 삶의 질 (IOI10_quality) C++14
100 / 100
 2350 ms 210760 KB 
#include<bits/stdc++.h>
#include "quality.h"

using namespace std;

const int MAXN=3005;
const int INF=1e9+5;

int n,m;
int h,w;
int half;
int pref[MAXN][MAXN];
int minPoss1[MAXN][MAXN];
int minPoss2[MAXN][MAXN];

bool check(int x,int q[][3001])
{
    pref[0][0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i>0 && j>0) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
            else if(i>0) pref[i][j]=pref[i-1][j];
            else if(j>0) pref[i][j]=pref[i][j-1];
            if(q[i][j]<x) pref[i][j]++;

            if(i>=h-1 && j>=w-1)
            {
                int a1=0,a2=0,b=0;
                if(i>=h) a1=pref[i-h][j];
                if(j>=w) a2=pref[i][j-w];
                if(i>=h && j>=w) b=pref[i-h][j-w];
                if(pref[i][j]-a1-a2+b>=half) return 1;
            }
        }
    }

    return 0;
}

int find_ans(int x,int q[][3001])
{
    deque<int> dq;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {//if(q[i][j]==x) cout<<i<<" "<<j<<endl;
            while(!dq.empty() && dq.front()<=j-w) dq.pop_front();
            if(q[i][j]>=x)
            {
                while(!dq.empty() && q[i][j]<q[i][dq.back()]) dq.pop_back();
                dq.push_back(j);
            }
            if(!dq.empty()) minPoss1[i][j]=q[i][dq.front()]; //
            else minPoss1[i][j]=INF;
            //if(minPoss[i][j]==x) cout<<i<<" "<<j<<endl;
        }
        while(!dq.empty()) dq.pop_back();
    }

    for(int j=0;j<m;j++)
    {
        for(int i=0;i<n;i++)
        {
            while(!dq.empty() && dq.front()<=i-h) dq.pop_front();
            if(minPoss1[i][j]>=x)
            {
                while(!dq.empty() && minPoss1[i][j]<minPoss1[dq.back()][j]) dq.pop_back();
                dq.push_back(i);
            }
            if(!dq.empty()) minPoss2[i][j]=minPoss1[dq.front()][j];
            else minPoss2[i][j]=INF;
            //if(minPoss[i][j]==x) cout<<i<<" "<<j<<" "<<dq.front()<<endl;
        }
        while(!dq.empty()) dq.pop_back();
    }

    int ans=INF;
    pref[0][0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i>0 && j>0) pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
            else if(i>0) pref[i][j]=pref[i-1][j];
            else if(j>0) pref[i][j]=pref[i][j-1];
            if(q[i][j]<x) pref[i][j]++;

            if(i>=h-1 && j>=w-1)
            {
                int a1=0,a2=0,b=0;
                if(i>=h) a1=pref[i-h][j];
                if(j>=w) a2=pref[i][j-w];
                if(i>=h && j>=w) b=pref[i-h][j-w];
                if(pref[i][j]-a1-a2+b>=half) ans=min(ans, minPoss2[i][j]); // cout<<pref[i][j]-a1-a2+b<<" "<<minPoss2[i][j]<<" "<<i<<" "<<j<<endl;
            }
        }
    }

    return ans;
}

int rectangle(int R,int C,int H,int W,int q[3001][3001])
{
    n=R, m=C;
    h=H, w=W;
    half=h*w/2;
    int l=1,r=n*m;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid,q)) r=mid;
        else l=mid+1;
    }
//cout<<l<<endl;
    return find_ans(l,q);
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2000 KB Output is correct
5 Correct 3 ms 2004 KB Output is correct
6 Correct 3 ms 2008 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2000 KB Output is correct
5 Correct 3 ms 2004 KB Output is correct
6 Correct 3 ms 2008 KB Output is correct
7 Correct 18 ms 6996 KB Output is correct
8 Correct 19 ms 7008 KB Output is correct
9 Correct 16 ms 6864 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2000 KB Output is correct
5 Correct 3 ms 2004 KB Output is correct
6 Correct 3 ms 2008 KB Output is correct
7 Correct 18 ms 6996 KB Output is correct
8 Correct 19 ms 7008 KB Output is correct
9 Correct 16 ms 6864 KB Output is correct
10 Correct 215 ms 38624 KB Output is correct
11 Correct 218 ms 38656 KB Output is correct
12 Correct 106 ms 27392 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 2 ms 2000 KB Output is correct
5 Correct 3 ms 2004 KB Output is correct
6 Correct 3 ms 2008 KB Output is correct
7 Correct 18 ms 6996 KB Output is correct
8 Correct 19 ms 7008 KB Output is correct
9 Correct 16 ms 6864 KB Output is correct
10 Correct 215 ms 38624 KB Output is correct
11 Correct 218 ms 38656 KB Output is correct
12 Correct 106 ms 27392 KB Output is correct
13 Correct 2350 ms 210760 KB Output is correct
14 Correct 2309 ms 210740 KB Output is correct
15 Correct 2133 ms 203524 KB Output is correct