oj.uz

답안 #410240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
410240 2021-05-22T10:23:44 Z pliam 삶의 질 (IOI10_quality) C++14
100 / 100
 2498 ms 121584 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXR 3005
#define MAXC 3005
#define INF (int)1e9

int height,width,rows,cols;
int q[3005][3005];
int cnt[3005];

bool check(int x){
    for(int c=1;c<=cols;c++){
        cnt[c]=0;
        for(int r=1;r<height;r++){
            cnt[c]+=(q[r][c]<=x);
        }
    }
    for(int r=1;r+height-1<=rows;r++){
        //update
        for(int c=1;c<=cols;c++){
            cnt[c]+=((q[r+height-1][c]<=x)-(q[r-1][c]<=x));
        }
        int ctr=0;
        for(int c=1;c<width;c++){
            ctr+=cnt[c];
        }
        //slide
        for(int c=1;c+width-1<=cols;c++){
            //update
            ctr+=(cnt[c+width-1]-cnt[c-1]);
            
            if(ctr>=((height*width+1)/2)){
                return true;
            }
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    rows=R;
	cols=C;
	height=H;
	width=W;
	for(int r=0;r<rows;r++){
        for(int c=0;c<cols;c++){
            q[r+1][c+1]=Q[r][c];
        }
    }
    for(int r=1;r<=rows;r++){
        q[r][0]=INF;
    }
    for(int c=1;c<=cols;c++){
        q[0][c]=INF;
    }
    
    //binary search
    int k=R*C;
    for(int b=R*C-1;b>0;b/=2){
        while(k-b>0&&check(k-b)) k-=b;
    }
    return k;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 15 ms 3904 KB Output is correct
8 Correct 15 ms 4012 KB Output is correct
9 Correct 14 ms 3772 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 15 ms 3904 KB Output is correct
8 Correct 15 ms 4012 KB Output is correct
9 Correct 14 ms 3772 KB Output is correct
10 Correct 167 ms 22836 KB Output is correct
11 Correct 174 ms 22880 KB Output is correct
12 Correct 90 ms 15656 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 552 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 15 ms 3904 KB Output is correct
8 Correct 15 ms 4012 KB Output is correct
9 Correct 14 ms 3772 KB Output is correct
10 Correct 167 ms 22836 KB Output is correct
11 Correct 174 ms 22880 KB Output is correct
12 Correct 90 ms 15656 KB Output is correct
13 Correct 2498 ms 121536 KB Output is correct
14 Correct 2060 ms 121584 KB Output is correct
15 Correct 1996 ms 116180 KB Output is correct