| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16956 |
2015-11-02T12:07:36 Z |
erdemkiraz |
UFO (IZhO14_ufo) |
C++ |
|
1259 ms |
205152 KB |
#ifdef D
#include "header.h"
#else
#include "bits/stdc++.h"
#endif
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;
const int N = 1e6 + 5;
int n, m, r, k, p;
class tree{ public:
int n;
vector < int > t;
void init(int n) {
this -> n = n;
t.resize(n * 4 + 5, 0);
}
void update(int x, int l, int r, int x1, int k) {
if(l == r) {
t[x] += k;
return;
}
int m = l + r >> 1;
if(x1 <= m)
update(x + x, l, m, x1, k);
else
update(x + x + 1, m + 1, r, x1, k);
t[x] = max(t[x + x], t[x + x + 1]);
}
int getL(int x, int l, int r, int i, int k) {
if(r < i or t[x] < k) {
return 0;
}
if(l == r)
return l;
int m = l + r >> 1;
int res = getL(x + x, l, m, i, k);
if(res)
return res;
return getL(x + x + 1, m + 1, r, i, k);
}
int getR(int x, int l, int r, int i, int k) {
if(i < l or t[x] < k) {
return 0;
}
if(l == r)
return l;
int m = l + r >> 1;
int res = getR(x + x + 1, m + 1, r, i, k);
if(res)
return res;
return getR(x + x, l, m, i, k);
}
void update(int x, int k) {
update(1, 1, n, x, k);
}
int getL(int i, int k) {
return getL(1, 1, n, i, k);
}
int getR(int i, int k) {
return getR(1, 1, n, i, k);
}
};
tree row[N], col[N];
vector < int > a[N], dp[N];
int main () {
scanf("%d %d %d %d %d", &n, &m, &r, &k, &p);
for(int i = 0; i <= n; i++) {
row[i].init(m);
a[i].resize(m + 1);
dp[i].resize(m + 1, 0);
}
for(int i = 1; i <= m; i++) {
col[i].init(n);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int x;
scanf("%d", &x);
a[i][j] = x;
row[i].update(j, x);
col[j].update(i, x);
}
}
for(int i = 1; i <= k; i++) {
char c;
int x, p;
scanf(" %c %d %d", &c, &x, &p);
if(c == 'W') {
int pos = 1;
for(int it = 0; it < r; it++) {
int nextPos = row[x].getL(pos, p);
if(!nextPos)
break;
row[x].update(nextPos, -1);
col[nextPos].update(x, -1);
a[x][nextPos]--;
pos = nextPos + 1;
}
}
if(c == 'E') {
int pos = m;
for(int it = 0; it < r; it++) {
int nextPos = row[x].getR(pos, p);
if(!nextPos)
break;
row[x].update(nextPos, -1);
col[nextPos].update(x, -1);
a[x][nextPos]--;
pos = nextPos - 1;
}
}
if(c == 'N') {
int pos = 1;
for(int it = 0; it < r; it++) {
int nextPos = col[x].getL(pos, p);
if(!nextPos)
break;
row[nextPos].update(x, -1);
col[x].update(nextPos, -1);
a[nextPos][x]--;
pos = nextPos + 1;
}
}
if(c == 'S') {
int pos = n;
for(int it = 0; it < r; it++) {
int nextPos = col[x].getR(pos, p);
if(!nextPos)
break;
row[nextPos].update(x, -1);
col[x].update(nextPos, -1);
a[nextPos][x]--;
pos = nextPos - 1;
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] = max(a[i][j], 0);
//printf("%d ", a[i][j]);
}
//puts("");
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];
}
}
int ans = 0;
for(int i = p; i <= n; i++) {
for(int j = p; j <= m; j++) {
ans = max(ans, dp[i][j] - dp[i - p][j] - dp[i][j - p] + dp[i - p][j - p]);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
ufo.cpp: In member function 'void tree::update(int, int, int, int, int)':
ufo.cpp:34:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
^
ufo.cpp: In member function 'int tree::getL(int, int, int, int, int)':
ufo.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
^
ufo.cpp: In member function 'int tree::getR(int, int, int, int, int)':
ufo.cpp:59:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
^
ufo.cpp: In function 'int main()':
ufo.cpp:81:48: 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:96:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
ufo.cpp:106:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %d %d", &c, &x, &p);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
111404 KB |
Output is correct |
| 2 |
Correct |
33 ms |
111404 KB |
Output is correct |
| 3 |
Correct |
33 ms |
111536 KB |
Output is correct |
| 4 |
Correct |
46 ms |
111800 KB |
Output is correct |
| 5 |
Correct |
113 ms |
113692 KB |
Output is correct |
| 6 |
Correct |
323 ms |
130628 KB |
Output is correct |
| 7 |
Correct |
476 ms |
155976 KB |
Output is correct |
| 8 |
Correct |
349 ms |
155976 KB |
Output is correct |
| 9 |
Correct |
606 ms |
153260 KB |
Output is correct |
| 10 |
Correct |
699 ms |
155976 KB |
Output is correct |
| 11 |
Correct |
516 ms |
155528 KB |
Output is correct |
| 12 |
Correct |
706 ms |
155976 KB |
Output is correct |
| 13 |
Correct |
866 ms |
158328 KB |
Output is correct |
| 14 |
Correct |
689 ms |
155528 KB |
Output is correct |
| 15 |
Correct |
826 ms |
155976 KB |
Output is correct |
| 16 |
Correct |
389 ms |
155528 KB |
Output is correct |
| 17 |
Correct |
1259 ms |
158328 KB |
Output is correct |
| 18 |
Correct |
473 ms |
152652 KB |
Output is correct |
| 19 |
Correct |
523 ms |
161492 KB |
Output is correct |
| 20 |
Correct |
1136 ms |
205152 KB |
Output is correct |
