| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58138 |
2018-07-17T01:16:38 Z |
Benq |
UFO (IZhO14_ufo) |
C++14 |
|
1341 ms |
163496 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
struct Seg {
int SZ;
vi seg;
void init(int _N) {
SZ = 1; while (SZ < _N) SZ *= 2;
seg.resize(2*SZ);
}
int comb(int a, int b) { return max(a,b); } // easily change this to min or max
int fst(int nex, int hei, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R = SZ-1;
if (seg[ind] < hei || nex > R) return MOD;
if (L == R) return L;
int M = (L+R)/2;
if (nex <= M) {
int x = fst(nex,hei,2*ind,L,M);
if (x != MOD) return x;
}
return fst(nex,hei,2*ind+1,M+1,R);
}
int lst(int nex, int hei, int ind = 1, int L = 0, int R = -1) {
if (R == -1) R = SZ-1;
if (seg[ind] < hei || nex < L) return -MOD;
if (L == R) return L;
int M = (L+R)/2;
if (nex > M) {
int x = lst(nex,hei,2*ind+1,M+1,R);
if (x != -MOD) return x;
}
return lst(nex,hei,2*ind,L,M);
}
void upd(int p, int value) { // set value at position p
for (seg[p += SZ] += value; p > 1; p >>= 1)
seg[p>>1] = comb(seg[p],seg[p^1]); // non-commutative operations
}
};
int N,M,R,K,P;
vector<Seg> hori, vert;
vector<vi> v;
void init() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> R >> K >> P;
v.resize(N);
F0R(i,N) {
v[i].resize(M);
F0R(j,M) cin >> v[i][j];
}
hori.resize(N), vert.resize(M);
F0R(i,N) {
hori[i].init(M);
F0R(j,M) hori[i].upd(j,v[i][j]);
}
F0R(j,M) {
vert[j].init(N);
F0R(i,N) {
vert[j].upd(i,v[i][j]);
// cout << "OH " << j << " " << i << " " << v[i][j] << "\n";
}
}
}
void sub(pi x) {
v[x.f][x.s] --;
hori[x.f].upd(x.s,-1);
vert[x.s].upd(x.f,-1);
}
int main() {
init();
F0R(i,K) {
char c; int pos, hei; cin >> c >> pos >> hei; pos --;
vpi change;
if (c == 'N') {
int nex = 0;
F0R(i,R) {
int t = vert[pos].fst(nex,hei);
if (t == MOD) break;
change.pb({t,pos});
nex = t+1;
}
} else if (c == 'S') {
int nex = N-1;
F0R(i,R) {
int t = vert[pos].lst(nex,hei);
if (t == -MOD) break;
change.pb({t,pos});
nex = t-1;
}
} else if (c == 'W') {
int nex = 0;
F0R(i,R) {
int t = hori[pos].fst(nex,hei);
if (t == MOD) break;
change.pb({pos,t});
nex = t+1;
}
} else if (c == 'E') {
int nex = M-1;
F0R(i,R) {
int t = hori[pos].lst(nex,hei);
if (t == -MOD) break;
change.pb({pos,t});
nex = t-1;
}
}
for (auto a: change) sub(a);
}
ll cum[sz(v)+1][sz(v[0])+1];
F0R(i,sz(v)+1) F0R(j,sz(v[0])+1) cum[i][j] = 0;
F0R(i,sz(v)) F0R(j,sz(v[0])) {
cum[i+1][j+1] = v[i][j]+cum[i+1][j]+cum[i][j+1]-cum[i][j];
}
ll ans = 0;
F0R(i,sz(v)+1-P) F0R(j,sz(v[0])+1-P) ans = max(ans,cum[i+P][j+P]-cum[i+P][j]-cum[i][j+P]+cum[i][j]);
/*F0R(i,N) {
F0R(j,M) cout << v[i][j] << " ";
cout << "\n";
}*/
cout << ans;
}
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
4 ms |
672 KB |
Output is correct |
| 4 |
Correct |
19 ms |
1164 KB |
Output is correct |
| 5 |
Correct |
125 ms |
3740 KB |
Output is correct |
| 6 |
Correct |
239 ms |
21932 KB |
Output is correct |
| 7 |
Correct |
321 ms |
52848 KB |
Output is correct |
| 8 |
Correct |
251 ms |
57428 KB |
Output is correct |
| 9 |
Correct |
514 ms |
58144 KB |
Output is correct |
| 10 |
Correct |
649 ms |
64448 KB |
Output is correct |
| 11 |
Correct |
427 ms |
64448 KB |
Output is correct |
| 12 |
Correct |
643 ms |
70936 KB |
Output is correct |
| 13 |
Correct |
776 ms |
78492 KB |
Output is correct |
| 14 |
Correct |
558 ms |
78492 KB |
Output is correct |
| 15 |
Correct |
668 ms |
83732 KB |
Output is correct |
| 16 |
Correct |
244 ms |
83732 KB |
Output is correct |
| 17 |
Correct |
1341 ms |
101016 KB |
Output is correct |
| 18 |
Correct |
253 ms |
101016 KB |
Output is correct |
| 19 |
Correct |
387 ms |
114020 KB |
Output is correct |
| 20 |
Correct |
1181 ms |
163496 KB |
Output is correct |
