oj.uz

Submission #367382

# Submission time Handle Problem Language Result Execution time Memory
367382 2021-02-17T05:14:11 Z ijxjdjd Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 167248 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;
        FR(i, R) FR(j, C) pref[i][j] = 0;
        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);
            }
        }
        for (int i = H-1; i < R; i++) {
            for (int j = W-1; j < C; j++) {
                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 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1388 KB Output is correct
5 Correct 4 ms 1388 KB Output is correct
6 Correct 5 ms 1388 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1388 KB Output is correct
5 Correct 4 ms 1388 KB Output is correct
6 Correct 5 ms 1388 KB Output is correct
7 Correct 40 ms 4320 KB Output is correct
8 Correct 41 ms 4320 KB Output is correct
9 Correct 36 ms 4192 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1388 KB Output is correct
5 Correct 4 ms 1388 KB Output is correct
6 Correct 5 ms 1388 KB Output is correct
7 Correct 40 ms 4320 KB Output is correct
8 Correct 41 ms 4320 KB Output is correct
9 Correct 36 ms 4192 KB Output is correct
10 Correct 684 ms 24136 KB Output is correct
11 Correct 695 ms 24172 KB Output is correct
12 Correct 309 ms 16212 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 4 ms 1388 KB Output is correct
5 Correct 4 ms 1388 KB Output is correct
6 Correct 5 ms 1388 KB Output is correct
7 Correct 40 ms 4320 KB Output is correct
8 Correct 41 ms 4320 KB Output is correct
9 Correct 36 ms 4192 KB Output is correct
10 Correct 684 ms 24136 KB Output is correct
11 Correct 695 ms 24172 KB Output is correct
12 Correct 309 ms 16212 KB Output is correct
13 Execution timed out 5051 ms 167248 KB Time limit exceeded
14 Halted 0 ms 0 KB -