oj.uz

Submission #367387

# Submission time Handle Problem Language Result Execution time Memory
367387 2021-02-17T05:22:30 Z ijxjdjd Quality Of Living (IOI10_quality) C++14
100 / 100
 3967 ms 141388 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 58 ms 35712 KB Output is correct
2 Correct 61 ms 35692 KB Output is correct
3 Correct 56 ms 35692 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35712 KB Output is correct
2 Correct 61 ms 35692 KB Output is correct
3 Correct 56 ms 35692 KB Output is correct
4 Correct 78 ms 36076 KB Output is correct
5 Correct 80 ms 36076 KB Output is correct
6 Correct 78 ms 36076 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35712 KB Output is correct
2 Correct 61 ms 35692 KB Output is correct
3 Correct 56 ms 35692 KB Output is correct
4 Correct 78 ms 36076 KB Output is correct
5 Correct 80 ms 36076 KB Output is correct
6 Correct 78 ms 36076 KB Output is correct
7 Correct 110 ms 37868 KB Output is correct
8 Correct 111 ms 37868 KB Output is correct
9 Correct 107 ms 37740 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35712 KB Output is correct
2 Correct 61 ms 35692 KB Output is correct
3 Correct 56 ms 35692 KB Output is correct
4 Correct 78 ms 36076 KB Output is correct
5 Correct 80 ms 36076 KB Output is correct
6 Correct 78 ms 36076 KB Output is correct
7 Correct 110 ms 37868 KB Output is correct
8 Correct 111 ms 37868 KB Output is correct
9 Correct 107 ms 37740 KB Output is correct
10 Correct 424 ms 51328 KB Output is correct
11 Correct 411 ms 51404 KB Output is correct
12 Correct 255 ms 45636 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35712 KB Output is correct
2 Correct 61 ms 35692 KB Output is correct
3 Correct 56 ms 35692 KB Output is correct
4 Correct 78 ms 36076 KB Output is correct
5 Correct 80 ms 36076 KB Output is correct
6 Correct 78 ms 36076 KB Output is correct
7 Correct 110 ms 37868 KB Output is correct
8 Correct 111 ms 37868 KB Output is correct
9 Correct 107 ms 37740 KB Output is correct
10 Correct 424 ms 51328 KB Output is correct
11 Correct 411 ms 51404 KB Output is correct
12 Correct 255 ms 45636 KB Output is correct
13 Correct 3931 ms 141388 KB Output is correct
14 Correct 3967 ms 141292 KB Output is correct
15 Correct 3557 ms 134468 KB Output is correct