oj.uz

답안 #288638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288638 2020-09-01T17:30:27 Z MasterTaster 삶의 질 (IOI10_quality) C++14
100 / 100
 2906 ms 127788 KB 
#include<bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
//#include "quality.h"

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"
#define MAXN 9000000

static int R,C,H,W,Q[3001][3001],ans;
int pref[3010][3010], q[3010][3010];
//int bit[310];
int pola;

bool check(int med, int R, int C, int H, int W)
{

    ///cout<<endl;
    for (int i=0; i<R; i++)
    {
        for (int j=0; j<C; j++)
        {
            pref[i][j]=0;
            if (q[i][j]<=med) pref[i][j]++;
            if (i>0) pref[i][j]+=pref[i-1][j];
            if (j>0) pref[i][j]+=pref[i][j-1];
            if (i>0 && j>0) pref[i][j]-=pref[i-1][j-1];
            ///cout<<pref[i][j]<<" ";
        }
        ///cout<<endl;
    }

    for (int i=H-1; i<R; i++)
    {
        for (int j=W-1; j<C; j++)
        {
            int koliko=pref[i][j];
            if (i>=H) koliko-=pref[i-H][j];
            if (j>=W) koliko-=pref[i][j-W];
            if (i>=H && j>=W) koliko+=pref[i-H][j-W];
            if (koliko>=pola) { return true; }
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    pola=H*W/2+1;
    for (int i=0; i<R; i++) for (int j=0; j<C; j++) q[i][j]=Q[i][j];

    int l=1, r=R*C;
    int ress=R*C;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        ///cout<<mid<<":"<<endl<<endl<<endl;
        if (check(mid, R, C, H, W))
        {
            ress=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ress;
}

Compilation message

quality.cpp:16:34: warning: 'ans' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],ans;
      |                                  ^~~
quality.cpp:16:20: warning: 'Q' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],ans;
      |                    ^
quality.cpp:16:18: warning: 'W' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],ans;
      |                  ^
quality.cpp:16:16: warning: 'H' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],ans;
      |                ^
quality.cpp:16:14: warning: 'C' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],ans;
      |              ^
quality.cpp:16:12: warning: 'R' defined but not used [-Wunused-variable]
   16 | static int R,C,H,W,Q[3001][3001],ans;
      |            ^

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 27 ms 5596 KB Output is correct
8 Correct 26 ms 5504 KB Output is correct
9 Correct 26 ms 5376 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 27 ms 5596 KB Output is correct
8 Correct 26 ms 5504 KB Output is correct
9 Correct 26 ms 5376 KB Output is correct
10 Correct 310 ms 30888 KB Output is correct
11 Correct 300 ms 30840 KB Output is correct
12 Correct 155 ms 21496 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 27 ms 5596 KB Output is correct
8 Correct 26 ms 5504 KB Output is correct
9 Correct 26 ms 5376 KB Output is correct
10 Correct 310 ms 30888 KB Output is correct
11 Correct 300 ms 30840 KB Output is correct
12 Correct 155 ms 21496 KB Output is correct
13 Correct 2902 ms 127788 KB Output is correct
14 Correct 2906 ms 117112 KB Output is correct
15 Correct 2618 ms 115792 KB Output is correct