답안 #92774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92774 2019-01-04T13:24:25 Z SamAnd UFO (IZhO14_ufo) C++17
70 / 100
2000 ms 59036 KB
#include <iostream>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
#define m_p make_pair
const int N = 1000006;

int n, m, r, k, P;
int** a;

int fun()
{
    long long** p;
    p = new long long*[n + 1];
    for (int i = 0; i <= n; ++i)
        p[i] = new long long[m + 1];
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            p[i][j] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
        }
    }
    long long ans = 0;
    for (int x1 = 1; x1 <= n - P + 1; ++x1)
    {
        int x2 = x1 + P - 1;
        for (int y1 = 1; y1 <= m - P + 1; ++y1)
        {
            int y2 = y1 + P - 1;
            //long long t = p[x2][y2] - p[x2][y1 - 1] - p[x1 - 1][y2] + p[x1 - 1][y1 - 1];
            long long t = 0;
            for (int i = x1; i <= x2; ++i)
            {
                for (int j = y1; j <= y2; ++j)
                {
                    t += a[i][j];
                }
            }
            ans = max(ans, t);
        }
    }
    return ans;
}

int *tx[N], *ty[N];

void bilx(int i, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        tx[i][pos] = a[i][tl];
        return;
    }
    int m = (tl + tr) / 2;
    bilx(i, tl, m, pos * 2);
    bilx(i, m + 1, tr, pos * 2 + 1);
    tx[i][pos] = max(tx[i][pos * 2], tx[i][pos * 2 + 1]);
}

void bily(int j, int tl, int tr, int pos)
{
    if (tl == tr)
    {
        ty[j][pos] = a[tl][j];
        return;
    }
    int m = (tl + tr) / 2;
    bily(j, tl, m, pos * 2);
    bily(j, m + 1, tr, pos * 2 + 1);
    ty[j][pos] = max(ty[j][pos * 2], ty[j][pos * 2 + 1]);
}

void ubdx(int i, int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        tx[i][pos]--;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubdx(i, tl, m, x, pos * 2);
    else
        ubdx(i, m + 1, tr, x, pos * 2 + 1);
    tx[i][pos] = max(tx[i][pos * 2], tx[i][pos * 2 + 1]);
}

void ubdy(int j, int tl, int tr, int x, int pos)
{
    if (tl == tr)
    {
        ty[j][pos]--;
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubdy(j, tl, m, x, pos * 2);
    else
        ubdy(j, m + 1, tr, x, pos * 2 + 1);
    ty[j][pos] = max(ty[j][pos * 2], ty[j][pos * 2 + 1]);
}

int qryx(int i, int tl, int tr, int l, int r, int pos)
{
    if (tl == l && tr == r)
        return tx[i][pos];
    int m = (tl + tr) / 2;
    if (r <= m)
        return qryx(i, tl, m, l, r, pos * 2);
    if (l > m)
        return qryx(i, m + 1, tr, l, r, pos * 2 + 1);
    return max(qryx(i, tl, m, l, m, pos * 2), qryx(i, m + 1, tr, m + 1, r, pos * 2 + 1));
}

int qryy(int j, int tl, int tr, int l, int r, int pos)
{
    if (tl == l && tr == r)
        return ty[j][pos];
    int m = (tl + tr) / 2;
    if (r <= m)
        return qryy(j, tl, m, l, r, pos * 2);
    if (l > m)
        return qryy(j, m + 1, tr, l, r, pos * 2 + 1);
    return max(qryy(j, tl, m, l, m, pos * 2), qryy(j, m + 1, tr, m + 1, r, pos * 2 + 1));
}

void pre()
{
    for (int i = 1; i <= n; ++i)
        tx[i] = new int[m * 4 + 1];
    for (int j = 1; j <= m; ++j)
        ty[j] = new int[n * 4 + 1];
    for (int i = 1; i <= n; ++i)
        bilx(i, 1, m, 1);
    for (int j = 1; j <= m; ++j)
        bily(j, 1, n, 1);
}

bool zz = true;
char tyz[N];
int xz[N], hz[N];

void solv1()
{
    pre();
    queue<pair<int, int> > q;
    for (int jj = 0; jj < k; ++jj)
    {
        char ty = tyz[jj];
        int x = xz[jj], h = hz[jj];
        if (ty == 'W')
        {
            int ll = 1;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = ll, r = m;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryx(x, 1, m, ll, mid, 1) >= h)
                        r = mid;
                    else
                        l = mid;
                }
                bool z = false;
                for (int mid = l; mid <= r; ++mid)
                {
                    if (qryx(x, 1, m, ll, mid, 1) >= h)
                    {
                        ll = mid + 1;
                        q.push(m_p(x, mid));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        else if (ty == 'E')
        {
            int rr = m;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = 1, r = rr;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryx(x, 1, m, mid, rr, 1) >= h)
                        l = mid;
                    else
                        r = mid;
                }
                bool z = false;
                for (int mid = r; mid >= l; --mid)
                {
                    if (qryx(x, 1, m, mid, rr, 1) >= h)
                    {
                        rr = mid - 1;
                        q.push(m_p(x, mid));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        else if (ty == 'N')
        {
            int ll = 1;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = ll, r = n;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryy(x, 1, n, ll, mid, 1) >= h)
                        r = mid;
                    else
                        l = mid;
                }
                bool z = false;
                for (int mid = l; mid <= r; ++mid)
                {
                    if (qryy(x, 1, n, ll, mid, 1) >= h)
                    {
                        ll = mid + 1;
                        q.push(m_p(mid, x));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        else
        {
            int rr = n;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = 1, r = rr;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryy(x, 1, n, mid, rr, 1) >= h)
                        l = mid;
                    else
                        r = mid;
                }
                bool z = false;
                for (int mid = r; mid >= l; --mid)
                {
                    if (qryy(x, 1, n, mid, rr, 1) >= h)
                    {
                        rr = mid - 1;
                        q.push(m_p(mid, x));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        while (!q.empty())
        {
            ubdx(q.front().first, 1, m, q.front().second, 1);
            ubdy(q.front().second, 1, n, q.front().first, 1);
            q.pop();
        }
        /*cout << endl;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
                cout << qryx(i, 1, m, j, j, 1).maxu << ' ';
            cout << endl;
        }
        cout << endl;*/
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            a[i][j] = qryx(i, 1, m, j, j, 1);
        }
    }
    cout << fun() << endl;
}

void solv2()
{
    pre();
    queue<pair<int, int> > q;
    for (int jj = 0; jj < k; ++jj)
    {
        char ty = tyz[jj];
        int x = xz[jj], h = hz[jj];
        if (ty == 'W')
        {
            int ll = 1, rr = m;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = ll, r = rr;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryx(x, 1, m, ll, mid, 1) >= h)
                        r = mid;
                    else
                        l = mid;
                }
                rr = r;
                bool z = false;
                for (int mid = l; mid <= r; ++mid)
                {
                    if (qryx(x, 1, m, ll, mid, 1) >= h)
                    {
                        ll = mid + 1;
                        q.push(m_p(x, mid));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        else if (ty == 'E')
        {
            int ll = 1, rr = m;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = ll, r = rr;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryx(x, 1, m, mid, rr, 1) >= h)
                        l = mid;
                    else
                        r = mid;
                }
                ll = l;
                bool z = false;
                for (int mid = r; mid >= l; --mid)
                {
                    if (qryx(x, 1, m, mid, rr, 1) >= h)
                    {
                        rr = mid - 1;
                        q.push(m_p(x, mid));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        else if (ty == 'N')
        {
            int ll = 1, rr = n;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = ll, r = rr;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryy(x, 1, n, ll, mid, 1) >= h)
                        r = mid;
                    else
                        l = mid;
                }
                rr = r;
                bool z = false;
                for (int mid = l; mid <= r; ++mid)
                {
                    if (qryy(x, 1, n, ll, mid, 1) >= h)
                    {
                        ll = mid + 1;
                        q.push(m_p(mid, x));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        else
        {
            int ll = 1, rr = n;
            for (int ii = 0; ii < r; ++ii)
            {
                int l = ll, r = rr;
                while ((r - l) > 3)
                {
                    int mid = (l + r) / 2;
                    if (qryy(x, 1, n, mid, rr, 1) >= h)
                        l = mid;
                    else
                        r = mid;
                }
                ll = l;
                bool z = false;
                for (int mid = r; mid >= l; --mid)
                {
                    if (qryy(x, 1, n, mid, rr, 1) >= h)
                    {
                        rr = mid - 1;
                        q.push(m_p(mid, x));
                        z = true;
                        break;
                    }
                }
                if (!z)
                    break;
            }
        }
        while (!q.empty())
        {
            ubdx(q.front().first, 1, m, q.front().second, 1);
            ubdy(q.front().second, 1, n, q.front().first, 1);
            q.pop();
        }
        /*cout << endl;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
                cout << qryx(i, 1, m, j, j, 1).maxu << ' ';
            cout << endl;
        }
        cout << endl;*/
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            a[i][j] = qryx(i, 1, m, j, j, 1);
        }
    }
    cout << fun() << endl;
}

int main()
{
    //freopen("ufo.in", "r", stdin);
    //freopen("ufo.out", "w", stdout);
    scanf(" %d %d %d %d %d", &n, &m, &r, &k, &P);
    a = new int*[n + 1];
    for (int i = 0; i <= n; ++i)
        a[i] = new int[m + 1];
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            scanf(" %d", &a[i][j]);
        }
    }
    for (int jj = 0; jj < k; ++jj)
    {
        scanf(" %c %d %d", &tyz[jj], &xz[jj], &hz[jj]);
        if (hz[jj] != 1)
            zz = false;
    }
    /////////////////////////////////
    if (zz)
        solv2();
    else
        solv1();
    return 0;
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:454:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d %d %d %d", &n, &m, &r, &k, &P);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:462:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~
ufo.cpp:467:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d", &tyz[jj], &xz[jj], &hz[jj]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 40 ms 1016 KB Output is correct
5 Correct 306 ms 3832 KB Output is correct
6 Correct 559 ms 25288 KB Output is correct
7 Correct 781 ms 51064 KB Output is correct
8 Correct 721 ms 47480 KB Output is correct
9 Incorrect 525 ms 45076 KB Output isn't correct
10 Correct 529 ms 46548 KB Output is correct
11 Incorrect 489 ms 43768 KB Output isn't correct
12 Correct 519 ms 46620 KB Output is correct
13 Correct 620 ms 53164 KB Output is correct
14 Correct 372 ms 43804 KB Output is correct
15 Execution timed out 2063 ms 39416 KB Time limit exceeded
16 Correct 843 ms 46840 KB Output is correct
17 Execution timed out 2069 ms 47224 KB Time limit exceeded
18 Correct 756 ms 48632 KB Output is correct
19 Execution timed out 2066 ms 42488 KB Time limit exceeded
20 Execution timed out 2062 ms 59036 KB Time limit exceeded