Submission #17547

#	Time	Username	Problem	Language	Result	Execution time	Memory
17547		ZiyaZa	UFO (IZhO14_ufo)	C++98	30 / 100	2000 ms	12312 KiB

ufo

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    //freopen ("ufo.in","r",stdin);
    //freopen ("ufo.out","w",stdout);
    int n,m,r,rm,rn,k,p,i,j,b,d,ans=0;
    char c;
    vector<vector<int> > a,l;
    cin>>n>>m>>r>>k>>p;
    rm=min(r,m);
    rn=min(r,n);
    a.resize(n);
    for (i=0;i<n;i++)
    {
        for (j=0;j<m;j++)
        {
            cin>>b;
            a[i].push_back(b);
        }
    }
    for (i=0;i<k;i++)
    {
        cin>>c>>b>>d;
        b--;
        if (c=='N')
        {
            for (j=0;j<n && rn>0;j++)
            {
                if (a[j][b]>=d)
                {
                    a[j][b]--;
                    rn--;
                }
            }
            rn=min(r,n);
        }
        else
        if (c=='S')
        {
            for (j=n-1;j>=0 && rn>0;j--)
            {
                if (a[j][b]>=d)
                {
                    a[j][b]--;
                    rn--;
                }
            }
            rn=min(r,n);
        }
        else
        if (c=='W')
        {
            for (j=0;rm>0 && j<m;j++)
            {
                if (a[b][j]>=d)
                {
                    a[b][j]--;
                    rm--;
                }
            }
            rm=min(r,m);
        }
        else
        {
            for (j=m-1;j>=0 && rm>0;j--)
            {
                if (a[b][j]>=d)
                {
                    a[b][j]--;
                    rm--;
                }
            }
            rm=min(r,m);
        }
    }
    l.resize(n);
    for (i=0;i<n;i++)
    {
        for (j=0;j<m;j++)
        {
            if (i==0 && j==0) l[i].push_back(a[i][j]);
            else
            if (i==0) l[i].push_back(l[i][j-1]+a[i][j]);
            else
            if (j==0) l[i].push_back(l[i-1][j]+a[i][j]);
            else l[i].push_back(a[i][j]+l[i-1][j]+l[i][j-1]-l[i-1][j-1]);
        }
    }
    ans=l[p-1][p-1];
    i=p-1;
    for (j=p;j<m;j++)
    {
        ans=max(ans,l[i][j]-l[i][j-p]);
    }
    j=p-1;
    for (i=p;i<n;i++)
    {
        ans=max(ans,l[i][j]-l[i-p][j]);
    }
    for (i=p;i<n;i++)
    {
        for (j=p;j<m;j++)
        {
            ans=max(ans,l[i][j]-l[i-p][j]-l[i][j-p]+l[i-p][j-p]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 30 / 100