oj.uz

답안 #258635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
258635 2020-08-06T09:40:00 Z uacoder123 삶의 질 (IOI10_quality) C++14
80 / 100
 5000 ms 210760 KB 
#include <bits/stdc++.h>
#include "quality.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int r,c,h,w,arr[3001][3001],pr[3001],p[3001][3001],ms[3001][3001];
int check(int m)
{
  memset(pr,0,sizeof(pr));
  memset(p,0,sizeof(p));
  memset(ms,0,sizeof(ms));
  int ch=0;
  for(int i=0;i<r;++i)
  {
    for(int j=0;j<c;++j)
    {
      if(arr[i][j]>m)
        p[i+1][j+1]=1;
      else if(arr[i][j]<m)
        p[i+1][j+1]=-1;
    }
  }
  int s=0;
  for(int i=0;i<r;++i)
  {
    for(int j=c-w;j<c;++j)
    {
      pr[i]+=p[i+1][j+1];
    }
    if(i>=h)
      s-=pr[i-h];
    s+=pr[i];
    if(i>=h-1)
    {
      ms[i][c-w]=s;
      if(s<=0)
        ch=1;
    }
  }
  for(int j=0;j<c;++j)
    for(int i=0;i<r;++i)
      p[i+1][j+1]+=p[i][j+1];
  for(int i=h-1;i<r;++i)
  {
    for(int j=c-w-1;j>=0;--j)
    {
      ms[i][j]=ms[i][j+1]-(p[i+1][j+w+1]-p[i-h+1][j+w+1])+p[i+1][j+1]-p[i+1-h][j+1];
      if(ms[i][j]<=0)
        ch=1;
    }
  }
  return(ch);
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) 
{
  r=R;
  c=C;
  h=H;
  w=W;
  for(int i=0;i<r;++i)
    for(int j=0;j<c;++j)
      arr[i][j]=Q[i][j];
  int le=1,ri=r*c,ans=r*c;
  while(le<=ri)
  {
    int mi=(le+ri)/2;
    if(check(mi))
    {
      ri=mi-1;
      ans=mi;
    }
    else
    {
      le=mi+1;
    }
  }
  return(ans);
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 71032 KB Output is correct
2 Correct 112 ms 71160 KB Output is correct
3 Correct 114 ms 71032 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 71032 KB Output is correct
2 Correct 112 ms 71160 KB Output is correct
3 Correct 114 ms 71032 KB Output is correct
4 Correct 148 ms 71800 KB Output is correct
5 Correct 139 ms 71672 KB Output is correct
6 Correct 147 ms 71800 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 71032 KB Output is correct
2 Correct 112 ms 71160 KB Output is correct
3 Correct 114 ms 71032 KB Output is correct
4 Correct 148 ms 71800 KB Output is correct
5 Correct 139 ms 71672 KB Output is correct
6 Correct 147 ms 71800 KB Output is correct
7 Correct 198 ms 74592 KB Output is correct
8 Correct 194 ms 74488 KB Output is correct
9 Correct 183 ms 74360 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 71032 KB Output is correct
2 Correct 112 ms 71160 KB Output is correct
3 Correct 114 ms 71032 KB Output is correct
4 Correct 148 ms 71800 KB Output is correct
5 Correct 139 ms 71672 KB Output is correct
6 Correct 147 ms 71800 KB Output is correct
7 Correct 198 ms 74592 KB Output is correct
8 Correct 194 ms 74488 KB Output is correct
9 Correct 183 ms 74360 KB Output is correct
10 Correct 558 ms 93432 KB Output is correct
11 Correct 546 ms 93648 KB Output is correct
12 Correct 350 ms 86008 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 71032 KB Output is correct
2 Correct 112 ms 71160 KB Output is correct
3 Correct 114 ms 71032 KB Output is correct
4 Correct 148 ms 71800 KB Output is correct
5 Correct 139 ms 71672 KB Output is correct
6 Correct 147 ms 71800 KB Output is correct
7 Correct 198 ms 74592 KB Output is correct
8 Correct 194 ms 74488 KB Output is correct
9 Correct 183 ms 74360 KB Output is correct
10 Correct 558 ms 93432 KB Output is correct
11 Correct 546 ms 93648 KB Output is correct
12 Correct 350 ms 86008 KB Output is correct
13 Execution timed out 5074 ms 210760 KB Time limit exceeded
14 Halted 0 ms 0 KB -