oj.uz

Submission #383858

# Submission time Handle Problem Language Result Execution time Memory
383858 2021-03-30T22:41:55 Z MODDI Quality Of Living (IOI10_quality) C++14
100 / 100
 3981 ms 210968 KB 
using namespace std;
#include <bits/stdc++.h>
#include "quality.h"
 
#pragma GCC optimize ("Ofast")
#pragma GCC target("avx2")
 
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
int pref[3001][3001];
pair<int, int> coords[3001*3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int low = 0;
    int high = R*C-1;
    FR(i, R){
        FR(j, C){
            coords[Q[i][j]-1] = {i, j};
        }
    }
 
    int base = H*W/2;
    while (low < high) {
        int mid = (low + high)/2;
        memset(pref, 0, sizeof(pref));
        FR(i, mid+1) {
            pref[coords[i].first][coords[i].second]++;
        }
        FR(i, R) {
            FR(j, C) {
                pref[i][j] += (i > 0 ? pref[i-1][j] : 0) + (j > 0 ? pref[i][j-1] : 0) - (i > 0 && j > 0 ? pref[i-1][j-1] : 0);
                if (pref[i][j] - (i >= H ? pref[i-H][j] : 0) - (j >= W ? pref[i][j-W] : 0) + (j >= W && i >= H ? pref[i-H][j-W] : 0) > base) {
                    high = mid;
                }
            }
        }
        if (high != mid) {
            low = mid+1;
        }
    }
    return high+1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 35692 KB Output is correct
2 Correct 59 ms 35692 KB Output is correct
3 Correct 54 ms 35692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 35692 KB Output is correct
2 Correct 59 ms 35692 KB Output is correct
3 Correct 54 ms 35692 KB Output is correct
4 Correct 73 ms 36144 KB Output is correct
5 Correct 73 ms 36076 KB Output is correct
6 Correct 74 ms 36076 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 35692 KB Output is correct
2 Correct 59 ms 35692 KB Output is correct
3 Correct 54 ms 35692 KB Output is correct
4 Correct 73 ms 36144 KB Output is correct
5 Correct 73 ms 36076 KB Output is correct
6 Correct 74 ms 36076 KB Output is correct
7 Correct 108 ms 37868 KB Output is correct
8 Correct 106 ms 38380 KB Output is correct
9 Correct 105 ms 38252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 35692 KB Output is correct
2 Correct 59 ms 35692 KB Output is correct
3 Correct 54 ms 35692 KB Output is correct
4 Correct 73 ms 36144 KB Output is correct
5 Correct 73 ms 36076 KB Output is correct
6 Correct 74 ms 36076 KB Output is correct
7 Correct 108 ms 37868 KB Output is correct
8 Correct 106 ms 38380 KB Output is correct
9 Correct 105 ms 38252 KB Output is correct
10 Correct 430 ms 58188 KB Output is correct
11 Correct 411 ms 58092 KB Output is correct
12 Correct 245 ms 48876 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 35692 KB Output is correct
2 Correct 59 ms 35692 KB Output is correct
3 Correct 54 ms 35692 KB Output is correct
4 Correct 73 ms 36144 KB Output is correct
5 Correct 73 ms 36076 KB Output is correct
6 Correct 74 ms 36076 KB Output is correct
7 Correct 108 ms 37868 KB Output is correct
8 Correct 106 ms 38380 KB Output is correct
9 Correct 105 ms 38252 KB Output is correct
10 Correct 430 ms 58188 KB Output is correct
11 Correct 411 ms 58092 KB Output is correct
12 Correct 245 ms 48876 KB Output is correct
13 Correct 3981 ms 210668 KB Output is correct
14 Correct 3932 ms 210968 KB Output is correct
15 Correct 3610 ms 196632 KB Output is correct