답안 #343845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
343845	2021-01-04T14:41:31 Z	apostoldaniel854	UFO (IZhO14_ufo)	C++14	45 / 100	973 ms	160876 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;
            col = m - col + 1;
            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;
            col = m - col + 1;
            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	384 KB	Output isn't correct
3	Incorrect	2 ms	504 KB	Output isn't correct
4	Incorrect	16 ms	1004 KB	Output isn't correct
5	Incorrect	139 ms	4076 KB	Output isn't correct
6	Incorrect	390 ms	33132 KB	Output isn't correct
7	Incorrect	704 ms	76524 KB	Output isn't correct
8	Correct	592 ms	76396 KB	Output is correct
9	Incorrect	685 ms	71720 KB	Output isn't correct
10	Correct	631 ms	76396 KB	Output is correct
11	Incorrect	591 ms	75756 KB	Output isn't correct
12	Correct	638 ms	76396 KB	Output is correct
13	Correct	596 ms	81132 KB	Output is correct
14	Correct	891 ms	75628 KB	Output is correct
15	Incorrect	702 ms	76284 KB	Output isn't correct
16	Correct	576 ms	75628 KB	Output is correct
17	Incorrect	973 ms	81020 KB	Output isn't correct
18	Correct	490 ms	72732 KB	Output is correct
19	Incorrect	612 ms	85740 KB	Output isn't correct
20	Correct	744 ms	160876 KB	Output is correct