Submission #107072

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
107072	2019-04-21T16:51:32 Z	SOIVIEONE	UFO (IZhO14_ufo)	C++14	45 / 100	568 ms	47424 KB

ufo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

int main()
{
	ll n, m, r, k, p;
	cin >> n >> m >> r >> k >> p;
	ll a[n+2][m+2];
	ll dp[n + 2][m + 2];
	memset(a, 0, sizeof a);
	memset(dp, 0, sizeof dp);	
	for(int i = 1; i <= n; i ++)
	for(int j = 1; j <= m; j ++)
		cin >> a[i][j];
	while(k --)
	{
		char t;
		ll x, y;
		cin >> t >> x >> y;
		if(t == 'W')
		{
			for(int i = 1; i <= min(m, r); i ++)
			{
				a[x][i] -= y;
				if(a[x][i] < 0)
					a[x][i] = 0;
			}
		}
		else
		if(t == 'E')
		{
			for(int i = m; i >= max(1ll,m - r + 1); i --)
			{
				a[x][i] -= y;
				if(a[x][i] < 0)
					a[x][i] = 0;
			}
		}
		else
		if(t == 'S')
		{
			for(int i = n; i >= max(n - r + 1,1ll); i --)
			{
				a[i][x] -= y;
				if(a[i][x] < 0)
					a[i][x] = 0;
			}
		}
		else
		{
			for(int i = 1; i <= min(n, r); i ++)
			{
				a[i][x] -= y;
				if(a[i][x] < 0)
					a[i][x] = 0;
			}
		}
	}
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			dp[i][j] = a[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
	ll ans = 0;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
		{
			if(i + p - 1 > n || j + p - 1 > m)
				continue;
			ll o = dp[i + p - 1][j + p - 1] - dp[i - 1][j + p - 1] - dp[i + p - 1][j - 1] + dp[i - 1][j - 1];
			umax(ans, o);
		}
	cout << ans;


	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Subtask #1

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Incorrect	2 ms	384 KB	Output isn't correct
3	Incorrect	3 ms	384 KB	Output isn't correct
4	Incorrect	15 ms	512 KB	Output isn't correct
5	Incorrect	41 ms	1280 KB	Output isn't correct
6	Incorrect	192 ms	8064 KB	Output isn't correct
7	Incorrect	455 ms	19196 KB	Output isn't correct
8	Correct	310 ms	19072 KB	Output is correct
9	Incorrect	308 ms	17536 KB	Output isn't correct
10	Correct	287 ms	19164 KB	Output is correct
11	Incorrect	348 ms	20344 KB	Output isn't correct
12	Correct	289 ms	19072 KB	Output is correct
13	Correct	359 ms	19072 KB	Output is correct
14	Correct	273 ms	19192 KB	Output is correct
15	Incorrect	335 ms	19072 KB	Output isn't correct
16	Correct	407 ms	19072 KB	Output is correct
17	Incorrect	568 ms	19192 KB	Output isn't correct
18	Correct	381 ms	17500 KB	Output is correct
19	Incorrect	328 ms	25312 KB	Output isn't correct
20	Correct	395 ms	47424 KB	Output is correct