답안 #154495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
154495 2019-09-22T07:56:14 Z srvlt UFO (IZhO14_ufo) C++14
65 / 100
2000 ms 149372 KB
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse2,avx")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
//#define int long long
using namespace std;

void dout() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, r, k, p;
typedef pair <int, int> pii;

void solve(int tc) {
    cin >> n >> m >> r >> k >> p;
    vector <vector <int> > g(n, vector <int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    if (n * m <= 50000 && k <= 5000) {
        for (int i = 0; i < k; i++) {
            char c;
            int x, y;
            cin >> c >> x >> y;
            x--;
            int cur = r;
            if (c == 'W') {
                for (int j = 0; j < m; j++) {
                    if (g[x][j] >= y) {
                        cur--;
                        g[x][j]--;
                    }
                    if (cur == 0) {
                        break;
                    }
                }
            }   else if (c == 'E') {
                for (int j = m - 1; j >= 0; j--) {
                    if (g[x][j] >= y) {
                        cur--;
                        g[x][j]--;
                    }
                    if (cur == 0) {
                        break;
                    }
                }
            }   else if (c == 'N') {
                for (int j = 0; j < n; j++) {
                    if (g[j][x] >= y) {
                        cur--;
                        g[j][x]--;
                    }
                    if (cur == 0) {
                        break;
                    }
                }
            }   else {
                for (int j = n - 1; j >= 0; j--) {
                    if (g[j][x] >= y) {
                        cur--;
                        g[j][x]--;
                    }
                    if (cur == 0) {
                        break;
                    }
                }
            }
        }
    }   else {
        set <pii> row[n], col[m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                row[i].insert({j, g[i][j]});
                col[j].insert({i, g[i][j]});
            }
        }
        for (int i = 0; i < k; i++) {
            char c;
            int x, y;
            cin >> c >> x >> y;
            x--;
            int cur = r;
            if (c == 'W') {
                while (cur > 0 && !row[x].empty()) {
                    pii z = *row[x].begin();
                    row[x].erase(z);
                    col[z.fi].erase({x, z.se});
                    z.se--;
                    g[x][z.fi]--;
                    if (z.se > 0) {
                        row[x].insert(z);
                        col[z.fi].insert({x, z.se});
                    }
                    cur--;
                }
            }   else if (c == 'E') {
                while (cur > 0 && !row[x].empty()) {
                    pii z = *(--row[x].end());
                    row[x].erase(z);
                    col[z.fi].erase({x, z.se});
                    z.se--;
                    g[x][z.fi]--;
                    if (z.se > 0) {
                        row[x].insert(z);
                        col[z.fi].insert({x, z.se});
                    }
                    cur--;
                }
            }   else if (c == 'N') {
                while (cur > 0 && !col[x].empty()) {
                    pii z = *col[x].begin();
                    col[x].erase(z);
                    row[z.fi].erase({x, z.se});
                    z.se--;
                    g[z.fi][x]--;
                    if (z.se > 0) {
                        col[x].insert(z);
                        row[z.fi].insert({x, z.se});
                    }
                    cur--;
                }
            }   else {
                while (cur > 0 && !col[x].empty()) {
                    pii z = *(--col[x].end());
                    col[x].erase(z);
                    row[z.fi].erase({x, z.se});
                    z.se--;
                    g[z.fi][x]--;
                    if (z.se > 0) {
                        col[x].insert(z);
                        row[z.fi].insert({x, z.se});
                    }
                    cur--;
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n - p + 1; i++) {
        for (int j = 0; j < m - p + 1; j++) {
            int tmp = 0;
            for (int h = i; h < i + p; h++) {
                for (int l = j; l < j + p; l++) {
                    tmp += g[h][l];
                }
            }
            res = max(res, tmp);
        }
    }
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Incorrect 26 ms 1400 KB Output isn't correct
5 Incorrect 160 ms 6136 KB Output isn't correct
6 Incorrect 526 ms 49972 KB Output isn't correct
7 Incorrect 1751 ms 106732 KB Output isn't correct
8 Correct 1427 ms 106812 KB Output is correct
9 Correct 1304 ms 103332 KB Output is correct
10 Correct 1323 ms 105504 KB Output is correct
11 Correct 940 ms 102700 KB Output is correct
12 Correct 1391 ms 105776 KB Output is correct
13 Correct 1731 ms 109332 KB Output is correct
14 Correct 1386 ms 101908 KB Output is correct
15 Incorrect 1603 ms 106200 KB Output isn't correct
16 Correct 1460 ms 105308 KB Output is correct
17 Execution timed out 2069 ms 108936 KB Time limit exceeded
18 Correct 1204 ms 98480 KB Output is correct
19 Incorrect 1418 ms 112176 KB Output isn't correct
20 Correct 1802 ms 149372 KB Output is correct