| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 154495 |
2019-09-22T07:56:14 Z |
srvlt |
UFO (IZhO14_ufo) |
C++14 |
|
2000 ms |
149372 KB |
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse2,avx")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
//#define int long long
using namespace std;
void dout() {
cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
cerr << H << ' ';
dout(T...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, r, k, p;
typedef pair <int, int> pii;
void solve(int tc) {
cin >> n >> m >> r >> k >> p;
vector <vector <int> > g(n, vector <int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
if (n * m <= 50000 && k <= 5000) {
for (int i = 0; i < k; i++) {
char c;
int x, y;
cin >> c >> x >> y;
x--;
int cur = r;
if (c == 'W') {
for (int j = 0; j < m; j++) {
if (g[x][j] >= y) {
cur--;
g[x][j]--;
}
if (cur == 0) {
break;
}
}
} else if (c == 'E') {
for (int j = m - 1; j >= 0; j--) {
if (g[x][j] >= y) {
cur--;
g[x][j]--;
}
if (cur == 0) {
break;
}
}
} else if (c == 'N') {
for (int j = 0; j < n; j++) {
if (g[j][x] >= y) {
cur--;
g[j][x]--;
}
if (cur == 0) {
break;
}
}
} else {
for (int j = n - 1; j >= 0; j--) {
if (g[j][x] >= y) {
cur--;
g[j][x]--;
}
if (cur == 0) {
break;
}
}
}
}
} else {
set <pii> row[n], col[m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
row[i].insert({j, g[i][j]});
col[j].insert({i, g[i][j]});
}
}
for (int i = 0; i < k; i++) {
char c;
int x, y;
cin >> c >> x >> y;
x--;
int cur = r;
if (c == 'W') {
while (cur > 0 && !row[x].empty()) {
pii z = *row[x].begin();
row[x].erase(z);
col[z.fi].erase({x, z.se});
z.se--;
g[x][z.fi]--;
if (z.se > 0) {
row[x].insert(z);
col[z.fi].insert({x, z.se});
}
cur--;
}
} else if (c == 'E') {
while (cur > 0 && !row[x].empty()) {
pii z = *(--row[x].end());
row[x].erase(z);
col[z.fi].erase({x, z.se});
z.se--;
g[x][z.fi]--;
if (z.se > 0) {
row[x].insert(z);
col[z.fi].insert({x, z.se});
}
cur--;
}
} else if (c == 'N') {
while (cur > 0 && !col[x].empty()) {
pii z = *col[x].begin();
col[x].erase(z);
row[z.fi].erase({x, z.se});
z.se--;
g[z.fi][x]--;
if (z.se > 0) {
col[x].insert(z);
row[z.fi].insert({x, z.se});
}
cur--;
}
} else {
while (cur > 0 && !col[x].empty()) {
pii z = *(--col[x].end());
col[x].erase(z);
row[z.fi].erase({x, z.se});
z.se--;
g[z.fi][x]--;
if (z.se > 0) {
col[x].insert(z);
row[z.fi].insert({x, z.se});
}
cur--;
}
}
}
}
int res = 0;
for (int i = 0; i < n - p + 1; i++) {
for (int j = 0; j < m - p + 1; j++) {
int tmp = 0;
for (int h = i; h < i + p; h++) {
for (int l = j; l < j + p; l++) {
tmp += g[h][l];
}
}
res = max(res, tmp);
}
}
cout << res;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc = 1;
// cin >> tc;
for (int i = 0; i < tc; i++) {
solve(i);
// cleanup();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
26 ms |
1400 KB |
Output isn't correct |
| 5 |
Incorrect |
160 ms |
6136 KB |
Output isn't correct |
| 6 |
Incorrect |
526 ms |
49972 KB |
Output isn't correct |
| 7 |
Incorrect |
1751 ms |
106732 KB |
Output isn't correct |
| 8 |
Correct |
1427 ms |
106812 KB |
Output is correct |
| 9 |
Correct |
1304 ms |
103332 KB |
Output is correct |
| 10 |
Correct |
1323 ms |
105504 KB |
Output is correct |
| 11 |
Correct |
940 ms |
102700 KB |
Output is correct |
| 12 |
Correct |
1391 ms |
105776 KB |
Output is correct |
| 13 |
Correct |
1731 ms |
109332 KB |
Output is correct |
| 14 |
Correct |
1386 ms |
101908 KB |
Output is correct |
| 15 |
Incorrect |
1603 ms |
106200 KB |
Output isn't correct |
| 16 |
Correct |
1460 ms |
105308 KB |
Output is correct |
| 17 |
Execution timed out |
2069 ms |
108936 KB |
Time limit exceeded |
| 18 |
Correct |
1204 ms |
98480 KB |
Output is correct |
| 19 |
Incorrect |
1418 ms |
112176 KB |
Output isn't correct |
| 20 |
Correct |
1802 ms |
149372 KB |
Output is correct |
