답안 #226289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
226289 2020-04-23T09:59:59 Z emil_physmath UFO (IZhO14_ufo) C++17
100 / 100
1628 ms 98604 KB
#include <iostream>
#include <vector>
using namespace std;

int shots;
int n, m;
vector<vector<int> > a;
vector<int> tcol[1000'000], trow[1000'000];

void Shoot(const vector<int>& t, int v, int vl, int vr, int hei, int dir, vector<int>& ans)
{
    if (ans.size() == shots) return;
    if (t[v] < hei) return;
    if (vl == vr)
    {
        ans.push_back(vr);
        return;
    }
    int vm = (vl + vr) / 2;
    if (dir == 1)
    {
        Shoot(t, v * 2, vl, vm, hei, dir, ans);
        Shoot(t, v * 2 + 1, vm + 1, vr, hei, dir, ans);
    }
    else
    {
        Shoot(t, v * 2 + 1, vm + 1, vr, hei, dir, ans);
        Shoot(t, v * 2, vl, vm, hei, dir, ans);
    }
}
void Add(vector<int>& t, int v, int vl, int vr, int i, int val)
{
    if (vl == vr)
    {
        t[v] += val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (i <= vm) Add(t, v * 2, vl, vm, i, val);
    else Add(t, v * 2 + 1, vm + 1, vr, i, val);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void SetRow(int i, int v, int vl, int vr)
{
    if (vl == vr)
    {
        a[i][vr] = trow[i][v];
        return;
    }
    int vm = (vl + vr) / 2;
    SetRow(i, v * 2, vl, vm);
    SetRow(i, v * 2 + 1, vm + 1, vr);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int qnum, anpetq;
    cin >> n >> m >> shots >> qnum >> anpetq;
    a.resize(n, vector<int>(m));
    for (int i = 0; i < n; ++i)
        trow[i].resize(4 * m);
    for (int j = 0; j < m; ++j)
        tcol[j].resize(4 * n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
        {
            cin >> a[i][j];
            Add(trow[i], 1, 0, m - 1, j, a[i][j]);
            Add(tcol[j], 1, 0, n - 1, i, a[i][j]);
        }
    while (qnum--)
    {
        char dir;
        int i, hei;
        cin >> dir >> i >> hei;
        int j = --i;
        vector<int> col;
        vector<int> row;
        if (dir == 'W')
            Shoot(trow[i], 1, 0, m - 1, hei, 1, col);
        else if (dir == 'E')
            Shoot(trow[i], 1, 0, m - 1, hei, -1, col);
        else if (dir == 'N')
            Shoot(tcol[j], 1, 0, n - 1, hei, 1, row);
        else // 'S'
            Shoot(tcol[j], 1, 0, n - 1, hei, -1, row);
        if (dir == 'W' || dir == 'E')
            for (int j: col)
            {
                Add(trow[i], 1, 0, m - 1, j, -1);
                Add(tcol[j], 1, 0, n - 1, i, -1);
            }
        else
            for (int i: row)
            {
                Add(trow[i], 1, 0, m - 1, j, -1);
                Add(tcol[j], 1, 0, n - 1, i, -1);
            }
    }
    for (int i = 0; i < n; ++i)
        SetRow(i, 1, 0, m - 1);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
#ifdef MANSON
            cerr << a[i][j] << ' ';
#endif
            if (i + anpetq - 1 >= n || j + anpetq - 1 >= m) continue;
            int cur = 0;
            for (int di = 0; di < anpetq; ++di)
                for (int dj = 0; dj < anpetq; ++dj)
                    cur += a[i + di][j + dj];
            ans = max(ans, cur);
        }
#ifdef MANSON
        cerr << '\n';
#endif
    }
    cout << ans;
}

Compilation message

ufo.cpp: In function 'void Shoot(const std::vector<int>&, int, int, int, int, int, std::vector<int>&)':
ufo.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ans.size() == shots) return;
         ~~~~~~~~~~~^~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47360 KB Output is correct
2 Correct 31 ms 47352 KB Output is correct
3 Correct 30 ms 47480 KB Output is correct
4 Correct 50 ms 47744 KB Output is correct
5 Correct 163 ms 49528 KB Output is correct
6 Correct 377 ms 64928 KB Output is correct
7 Correct 480 ms 84516 KB Output is correct
8 Correct 401 ms 84464 KB Output is correct
9 Correct 719 ms 83736 KB Output is correct
10 Correct 931 ms 84488 KB Output is correct
11 Correct 677 ms 83412 KB Output is correct
12 Correct 941 ms 84516 KB Output is correct
13 Correct 1108 ms 87620 KB Output is correct
14 Correct 993 ms 83360 KB Output is correct
15 Correct 1143 ms 84508 KB Output is correct
16 Correct 418 ms 83356 KB Output is correct
17 Correct 1574 ms 87628 KB Output is correct
18 Correct 404 ms 84328 KB Output is correct
19 Correct 558 ms 85992 KB Output is correct
20 Correct 1628 ms 98604 KB Output is correct