답안 #343822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343822	2021-01-04T14:15:59 Z	apostoldaniel854	UFO (IZhO14_ufo)	C++14	45 / 100	976 ms	165628 KB

ufo

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 3e4;

struct BestSegTree {
    vector <int> seg;
    int n;
    void init (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
    }
    void update (int node, int lb, int rb, int pos, int to_add) {
        if (lb == rb) {
            seg[node] += to_add;
            return;
        }
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (pos <= mid)
            update (left_node, lb, mid, pos, to_add);
        else
            update (right_node, mid + 1, rb, pos, to_add);
        seg[node] = max (seg[left_node], seg[right_node]);
    }
    int query (int node, int lb, int rb, int bound) {
        if (lb == rb)
            return lb;
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (seg[left_node] >= bound)
            return query (left_node, lb, mid, bound);
        if (seg[right_node] >= bound)
            return query (left_node, mid + 1, rb, bound);
        return -1;
    }
    int queryPos (int node, int lb, int rb, int pos) {
        if (lb == rb)
            return seg[node];
        int mid = (lb + rb) / 2, left_node = node * 2, right_node = node * 2 + 1;
        if (pos <= mid)
            return queryPos (left_node, lb, mid, pos);
        else
            return queryPos (right_node, mid + 1, rb, pos);
    }
};
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, m, r, k, p;
    cin >> n >> m >> r >> k >> p;
    vector <BestSegTree> segW (n + 1), segE (n + 1);
    for (int i = 1; i <= n; i++)
        segW[i].init (m), segE[i].init (m);
    vector <BestSegTree> segS (m + 1), segN (m + 1);
    for (int i = 1; i <= m; i++)
        segS[i].init (n), segN[i].init (n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            segS[j].update (1, 1, n, i, x);
            segN[j].update (1, 1, n, n - i + 1, x);
            segW[i].update (1, 1, m, j, x);
            segE[i].update (1, 1, m, m - j + 1, x);
        }
    }
    while (k--) {
        char dir;
        cin >> dir;
        if (dir == 'W') {
            int row, height;
            cin >> row >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int col = segW[row].query (1, 1, m, height);
                if (col == -1)
                    good = false;
                else {
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
        if (dir == 'E') {
            int row, height;
            cin >> row >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int col = segE[row].query (1, 1, m, height);
                if (col == -1)
                    good = false;
                else {
                    col = m - col + 1;
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
        if (dir == 'S') {
            int col, height;
            cin >> col >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int row = segS[col].query (1, 1, n, height);
                if (row == -1)
                    good = false;
                else {
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
        if (dir == 'N') {
            int col, height;
            cin >> col >> height;
            int lft = r;
            bool good = true;
            while (lft && good) {
                int row = segN[col].query (1, 1, n, height);
                if (row == -1)
                    good = false;
                else {
                    row = n - row + 1;
                    segS[col].update (1, 1, n, row, -1);
                    segN[col].update (1, 1, n, n - row + 1, -1);
                    segW[row].update (1, 1, m, col, -1);
                    segE[row].update (1, 1, m, m - col + 1, -1);
                }
                lft--;
            }
        }
    }
    vector <vector <int>> a (n + 1);
    for (int i = 1; i <= n; i++) {
        a[i].resize (m + 1);
        for (int j = 1; j <= m; j++)
            a[i][j] = segW[i].queryPos (1, 1, m, j);
    }
    int mx = 0;
    for (int i = 1; i <= n - p + 1; i++)
        for (int j = 1; j <= m - p + 1; j++) {
            int cnt = 0;
            for (int x = i; x < i + p; x++)
                for (int y = j; y < j + p; y++)
                    cnt += a[x][y];
            mx = max (mx, cnt);
        }
    cout << mx << "\n";
    return 0;
}

Subtask #1

45.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	364 KB	Output isn't correct
3	Incorrect	2 ms	512 KB	Output isn't correct
4	Incorrect	16 ms	1144 KB	Output isn't correct
5	Incorrect	144 ms	4972 KB	Output isn't correct
6	Incorrect	398 ms	36460 KB	Output isn't correct
7	Incorrect	723 ms	84332 KB	Output isn't correct
8	Correct	597 ms	80748 KB	Output is correct
9	Incorrect	688 ms	75244 KB	Output isn't correct
10	Correct	640 ms	79884 KB	Output is correct
11	Incorrect	587 ms	78828 KB	Output isn't correct
12	Correct	653 ms	79980 KB	Output is correct
13	Correct	609 ms	85484 KB	Output is correct
14	Correct	889 ms	78956 KB	Output is correct
15	Incorrect	702 ms	81388 KB	Output isn't correct
16	Correct	589 ms	80980 KB	Output is correct
17	Incorrect	976 ms	89836 KB	Output isn't correct
18	Correct	477 ms	78236 KB	Output is correct
19	Incorrect	621 ms	90732 KB	Output isn't correct
20	Correct	746 ms	165628 KB	Output is correct