oj.uz

Submission #367384

# Submission time Handle Problem Language Result Execution time Memory
367384 2021-02-17T05:16:36 Z ijxjdjd Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 167204 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];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int low = 0;
    int high = R*C-1;
    vector<pair<int, int>> coords;
    FR(i, R){
        FR(j, C){
            coords.push_back({i, j});
        }
    }
    auto comp = [&] (const auto& lhs, const auto& rhs) {
        return Q[lhs.first][lhs.second] < Q[rhs.first][rhs.second];
    };
    auto sum = [&] (int i, int j) {
        return 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);
    };
    sort(all(coords), comp);
    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 (sum(i, j) > 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 56 ms 35692 KB Output is correct
2 Correct 61 ms 35820 KB Output is correct
3 Correct 57 ms 35820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35692 KB Output is correct
2 Correct 61 ms 35820 KB Output is correct
3 Correct 57 ms 35820 KB Output is correct
4 Correct 80 ms 36204 KB Output is correct
5 Correct 79 ms 36224 KB Output is correct
6 Correct 78 ms 36204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35692 KB Output is correct
2 Correct 61 ms 35820 KB Output is correct
3 Correct 57 ms 35820 KB Output is correct
4 Correct 80 ms 36204 KB Output is correct
5 Correct 79 ms 36224 KB Output is correct
6 Correct 78 ms 36204 KB Output is correct
7 Correct 127 ms 37984 KB Output is correct
8 Correct 131 ms 37984 KB Output is correct
9 Correct 127 ms 37856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35692 KB Output is correct
2 Correct 61 ms 35820 KB Output is correct
3 Correct 57 ms 35820 KB Output is correct
4 Correct 80 ms 36204 KB Output is correct
5 Correct 79 ms 36224 KB Output is correct
6 Correct 78 ms 36204 KB Output is correct
7 Correct 127 ms 37984 KB Output is correct
8 Correct 131 ms 37984 KB Output is correct
9 Correct 127 ms 37856 KB Output is correct
10 Correct 829 ms 51528 KB Output is correct
11 Correct 805 ms 51612 KB Output is correct
12 Correct 414 ms 45652 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 35692 KB Output is correct
2 Correct 61 ms 35820 KB Output is correct
3 Correct 57 ms 35820 KB Output is correct
4 Correct 80 ms 36204 KB Output is correct
5 Correct 79 ms 36224 KB Output is correct
6 Correct 78 ms 36204 KB Output is correct
7 Correct 127 ms 37984 KB Output is correct
8 Correct 131 ms 37984 KB Output is correct
9 Correct 127 ms 37856 KB Output is correct
10 Correct 829 ms 51528 KB Output is correct
11 Correct 805 ms 51612 KB Output is correct
12 Correct 414 ms 45652 KB Output is correct
13 Execution timed out 5083 ms 167204 KB Time limit exceeded
14 Halted 0 ms 0 KB -