oj.uz

Submission #722312

# Submission time Handle Problem Language Result Execution time Memory
722312 2023-04-11T18:08:03 Z ktkerem Quality Of Living (IOI10_quality) C++17
100 / 100
 1502 ms 140232 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
#include "quality.h"
typedef int ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;  
const ll limit = 1e9+7;
const ll sus = 5e4+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll rectangle(ll r , ll c , ll h , ll w , ll q[3001][3001]){
  ll prf[r][c];
  ll lk = h*w/2 , rk = r*c/2+1;
  ll ss = h * w / 2 + 1;
  while(rk > lk){
    ll md = (lk + rk)/2;
    ll kd = 0;
    for(ll i = 0;r>i;i++){
      for(ll j = 0;c>j;j++){
        prf[i][j] = (q[i][j] <= md?1:0);
        if(i > 0){
          prf[i][j] += prf[i-1][j];
        }
        if(j > 0){
          prf[i][j] += prf[i][j-1];
        }
        if(i > 0 && j > 0){
          prf[i][j] -= prf[i-1][j-1];
        }
        if(h<=i+1 && w <= j+1){
          ll o = prf[i][j];
          if(i - h >= 0){
            o-= prf[i-h][j];
          }
          if(j - w>=0){
            o-= prf[i][j-w];
          }
          if(i - h >= 0 && j - w>=0){
            o+= prf[i-h][j-w];
          }
          if(o >= ss){
            kd = 1;
          }
        }
      }
    }
    if(kd){
      rk = md;
    }
    else{
      lk = md+1;
    }
  }
  return lk;
}
/*void solve(){
  ll **ar = new ll*[5];
  for(ll i = 0;5>i;i++){
    ar[i] = new ll [5];
  }
  for(ll i = 0 ; 5>i;i++){
    for(ll j = 0;5>j;j++){
      std::cin >> ar[i][j];
    }
  }
  std::cout << rectangle(5 , 5 , 3 , 3 , ar);
  return;
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  #ifndef ONLINE_JUDGE
    freopen("in.txt" , "r" , stdin);
    freopen("out.txt" , "w" , stdout);
  #endif
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}*/

Compilation message

quality.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 12 ms 2732 KB Output is correct
8 Correct 13 ms 2644 KB Output is correct
9 Correct 12 ms 2584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 12 ms 2732 KB Output is correct
8 Correct 13 ms 2644 KB Output is correct
9 Correct 12 ms 2584 KB Output is correct
10 Correct 160 ms 18868 KB Output is correct
11 Correct 154 ms 18860 KB Output is correct
12 Correct 79 ms 11496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 12 ms 2732 KB Output is correct
8 Correct 13 ms 2644 KB Output is correct
9 Correct 12 ms 2584 KB Output is correct
10 Correct 160 ms 18868 KB Output is correct
11 Correct 154 ms 18860 KB Output is correct
12 Correct 79 ms 11496 KB Output is correct
13 Correct 1502 ms 140232 KB Output is correct
14 Correct 1457 ms 140232 KB Output is correct
15 Correct 1350 ms 129600 KB Output is correct