Submission #17547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
17547	2015-12-25T20:52:17 Z	ZiyaZa	UFO (IZhO14_ufo)	C++	30 / 100	2000 ms	12312 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2180 KB	Output is correct
2	Correct	0 ms	2180 KB	Output is correct
3	Correct	0 ms	2180 KB	Output is correct
4	Correct	3 ms	2312 KB	Output is correct
5	Correct	19 ms	2804 KB	Output is correct
6	Correct	103 ms	7856 KB	Output is correct
7	Execution timed out	2000 ms	7884 KB	Execution timed out
8	Execution timed out	2000 ms	7884 KB	Execution timed out
9	Execution timed out	2000 ms	7668 KB	Execution timed out
10	Execution timed out	2000 ms	7884 KB	Execution timed out
11	Execution timed out	2000 ms	6852 KB	Execution timed out
12	Execution timed out	2000 ms	7884 KB	Execution timed out
13	Execution timed out	2000 ms	12312 KB	Execution timed out
14	Execution timed out	2000 ms	10980 KB	Execution timed out
15	Execution timed out	2000 ms	7884 KB	Execution timed out
16	Execution timed out	2000 ms	6852 KB	Execution timed out
17	Execution timed out	2000 ms	12312 KB	Execution timed out
18	Execution timed out	2000 ms	10540 KB	Execution timed out
19	Execution timed out	2000 ms	8376 KB	Execution timed out
20	Execution timed out	2000 ms	8364 KB	Execution timed out