oj.uz

답안 #407441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
407441 2021-05-19T00:47:48 Z soba 삶의 질 (IOI10_quality) C++14
100 / 100
 3110 ms 140216 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=1 , r= 3000*3000 , m , ans=r ;
	int arr[R+1][C+1]={0};
	int x;
	bool flag;
	while(l<=r)
    {
        m=(l+r)>>1;
        memset(arr , 0 , sizeof arr);
        for(int i = 0 ; i  < R ;  i++)
        {
            for(int j = 0 ; j < C ;j++)
            {
                if(Q[i][j]<=m)
                {
                    arr[i+1][j+1]=1;
                }
            }
        }
        for(int i = 1 ; i <= R ; i++)
        {
            for(int j = 1 ; j <=C ; j++)
            {
                arr[i][j]+= arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
            }
        }
//        for(int i = 1 ; i <= R ; i++)
//        {
//            for(int j = 1 ; j <=C ; j++)
//            {
//                arr[i][j]+=arr[i-1][j];
//            }
//        }
        flag=false;
      //  cout << "checking mid = " << m << ":-\n";
        for(int i = H ; i <=R ; i++)
        {
            for(int j = W ; j<=C ; j++)
            {
                //cout << "in " << i << " " << j << " = " ;
                x=arr[i][j]+arr[i-H][j-W]-arr[i-H][j]-arr[i][j-W];
                //cout << x << "\n";
                if(x>=(H*W)-x)
                {
                    flag=true;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    return ans;

}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 27 ms 2620 KB Output is correct
8 Correct 27 ms 2664 KB Output is correct
9 Correct 25 ms 2604 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 27 ms 2620 KB Output is correct
8 Correct 27 ms 2664 KB Output is correct
9 Correct 25 ms 2604 KB Output is correct
10 Correct 318 ms 18784 KB Output is correct
11 Correct 325 ms 18856 KB Output is correct
12 Correct 165 ms 11508 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 27 ms 2620 KB Output is correct
8 Correct 27 ms 2664 KB Output is correct
9 Correct 25 ms 2604 KB Output is correct
10 Correct 318 ms 18784 KB Output is correct
11 Correct 325 ms 18856 KB Output is correct
12 Correct 165 ms 11508 KB Output is correct
13 Correct 3110 ms 140196 KB Output is correct
14 Correct 3075 ms 140216 KB Output is correct
15 Correct 2824 ms 129440 KB Output is correct