oj.uz

Submission #367383

# Submission time Handle Problem Language Result Execution time Memory
367383 2021-02-17T05:15:32 Z ijxjdjd Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 167132 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);
                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 4 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 4 ms 1388 KB Output is correct
7 Correct 40 ms 4320 KB Output is correct
8 Correct 42 ms 4348 KB Output is correct
9 Correct 35 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 4 ms 1388 KB Output is correct
7 Correct 40 ms 4320 KB Output is correct
8 Correct 42 ms 4348 KB Output is correct
9 Correct 35 ms 4192 KB Output is correct
10 Correct 652 ms 24076 KB Output is correct
11 Correct 703 ms 24200 KB Output is correct
12 Correct 307 ms 16248 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 4 ms 1388 KB Output is correct
7 Correct 40 ms 4320 KB Output is correct
8 Correct 42 ms 4348 KB Output is correct
9 Correct 35 ms 4192 KB Output is correct
10 Correct 652 ms 24076 KB Output is correct
11 Correct 703 ms 24200 KB Output is correct
12 Correct 307 ms 16248 KB Output is correct
13 Execution timed out 5031 ms 167132 KB Time limit exceeded
14 Halted 0 ms 0 KB -