답안 #90690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90690 2018-12-23T16:16:27 Z popovicirobert UFO (IZhO14_ufo) C++14
40 / 100
767 ms 201468 KB
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

struct SegTree {
    vector <int> aint;
    int n;
    inline void init(int _n) {
        n = _n;
        aint.resize(4 * n + 1);
    }
    inline void refresh(int nod) {
        aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
    }
    void update(int nod, int left, int right, int pos, int val) {
        if(left == right) {
            aint[nod] = val;
        }
        else {
            int mid = (left + right) / 2;
            if(pos <= mid) update(2 * nod, left, mid, pos, val);
            else update(2 * nod + 1, mid + 1, right, pos, val);
            refresh(nod);
        }
    }
    int query_l(int nod, int left, int right, int l, int r, int val) {
        if(l <= left && right <= r) {
            int mid = (left + right) / 2;
            if(aint[nod] < val) {
                return -1;
            }
            if(left == right) {
                return left;
            }
            if(aint[2 * nod] >= val) {
                return query_l(2 * nod, left, mid, l, r, val);
            }
            return query_l(2 * nod + 1, mid + 1, right, l, r, val);
        }
        else {
            int mid = (left + right) / 2;
            int ans = -1;
            if(l <= mid && aint[2 * nod] >= val) {
                ans = query_l(2 * nod, left, mid, l, r, val);
            }
            if(mid < r && ans == -1 && aint[2 * nod + 1] >= val) {
                ans = query_l(2 * nod + 1, mid + 1, right, l, r, val);
            }
            return ans;
        }
    }
    int query_r(int nod, int left, int right, int l, int r, int val) {
        if(l <= left && right <= r) {
            int mid = (left + right) / 2;
            if(aint[nod] < val) {
                return -1;
            }
            if(left == right) {
                return left;
            }
            if(aint[2 * nod + 1] >= val) {
                return query_r(2 * nod + 1, mid + 1, right, l, r, val);
            }
            return query_r(2 * nod, left, mid, l, r, val);
        }
        else {
            int mid = (left + right) / 2;
            int ans = -1;
            if(mid < r && aint[2 * nod + 1] >= val) {
                ans = query_r(2 * nod + 1, mid + 1, right, l, r, val);
            }
            if(l <= mid && ans == -1 && aint[2 * nod] >= val) {
                ans = query_r(2 * nod, left, mid, l, r, val);
            }
            return ans;
        }
    }
};

vector < vector <ll> > mat;
vector < SegTree > row, col;

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, m, r, k, p;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> r >> k >> p;
    mat.resize(n + 1);
    row.resize(n + 1), col.resize(m + 1);
    for(i = 1; i <= n; i++) {
        row[i].init(m);
    }
    for(i = 1; i <= m; i++) {
        col[i].init(n);
    }
    mat[0].resize(m + 1);
    for(i = 1; i <= n; i++) {
        mat[i].resize(m + 1);
        for(j = 1; j <= m; j++) {
            cin >> mat[i][j];
            row[i].update(1, 1, m, j, mat[i][j]);
            col[j].update(1, 1, n, i, mat[i][j]);
        }
    }
    while(k > 0) {
        k--;
        int id, h;
        char ch;
        cin >> ch >> id >> h;
        if(ch == 'N') {
            int pos = 0;
            i = 0;
            while(i < r && pos < n) {
                pos = col[id].query_l(1, 1, n, pos + 1, n, h);
                if(pos == -1) {
                    break;
                }
                mat[pos][id]--;
                col[id].update(1, 1, n, pos, mat[pos][id]);
                i++;
            }
        }
        if(ch == 'S') {
            int pos = n + 1;
            i = 0;
            while(i < r && pos > 1) {
                pos = col[id].query_r(1, 1, n, 1, pos - 1, h);
                if(pos == -1) {
                    break;
                }
                mat[pos][id]--;
                col[id].update(1, 1, n, pos, mat[pos][id]);
                i++;
            }
        }
        if(ch == 'W') {
            int pos = 0;
            i = 0;
            while(i < r && pos < m) {
                pos = row[id].query_l(1, 1, n, pos + 1, m, h);
                if(pos == -1) {
                    break;
                }
                mat[id][pos]--;
                row[id].update(1, 1, n, pos, mat[id][pos]);
                i++;
            }
        }
        if(ch == 'E') {
            int pos = m + 1;
            i = 0;
            while(i < r && pos > 1) {
                pos = row[id].query_l(1, 1, n, 1, pos - 1, h);
                if(pos == -1) {
                    break;
                }
                mat[id][pos]--;
                row[id].update(1, 1, n, pos, mat[id][pos]);
                i++;
            }
        }
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
        }
    }
    ll ans = 0;
    for(i = p; i <= n; i++) {
        for(j = p; j <= m; j++) {
            ans = max(ans, mat[i][j] - mat[i - p][j] - mat[i][j - p] + mat[i - p][j - p]);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 292 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Correct 3 ms 620 KB Output is correct
4 Incorrect 10 ms 1284 KB Output isn't correct
5 Correct 32 ms 3820 KB Output is correct
6 Incorrect 189 ms 24108 KB Output isn't correct
7 Runtime error 266 ms 100276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 226 ms 104428 KB Output is correct
9 Runtime error 310 ms 104428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 251 ms 108792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 236 ms 110404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 267 ms 113044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 599 ms 120608 KB Output is correct
14 Runtime error 243 ms 120608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 282 ms 122772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 247 ms 127744 KB Output is correct
17 Incorrect 767 ms 140188 KB Output isn't correct
18 Correct 253 ms 141924 KB Output is correct
19 Incorrect 257 ms 153012 KB Output isn't correct
20 Correct 299 ms 201468 KB Output is correct