| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 341281 |
2020-12-29T10:54:32 Z |
amunduzbaev |
UFO (IZhO14_ufo) |
C++14 |
|
1042 ms |
162264 KB |
/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define int long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
const int N = 1e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int n, m, k, ans = 1, cnt, rr, p;
vector<vii> aa;
struct TREE{
vector<int> tree;
int s = 2;
void init(int n, vector<int> vv){
while(s < n) s<<=1;
tree.assign(s*2, 0);
for(int i=s;i<s+sz(vv);i++) tree[i] = vv[i-s];
for(int i=s-1;i>=1;i--) tree[i] = max(tree[i<<1], tree[(i<<1)+1]);
}
vector<int> dd;
int rr;
void dec(int hh, int lx, int rx, int x){
if(!rr) return;
if(lx == rx){
dd.pb(lx);
tree[x]--;
rr--;
return;
}
int m = (lx + rx)>>1;
if(tree[x<<1] >= hh) dec(hh, lx, m, x<<1);
tree[x] = max(tree[(x<<1)], tree[(x<<1)+1]);
if(!rr) return;
if(tree[(x<<1)+1] >= hh) dec(hh, m+1, rx, (x<<1) +1);
tree[x] = max(tree[(x<<1)], tree[(x<<1)+1]);
}
void decr(int hh){
dd.clear();
dec(hh, 1, s, 1);
}
void rdec(int hh, int lx, int rx, int x){
//cout<<lx<<" "<<rx<<" "<<tree[x]<<" "<<rr<<endl;
if(lx == rx){
dd.pb(lx);
tree[x]--;
rr--;
return;
}
int m = (lx + rx)>>1;
if(tree[(x<<1)+1] >= hh) rdec(hh, m+1, rx, (x<<1) +1);
tree[x] = max(tree[(x<<1)], tree[(x<<1)+1]);
if(!rr) return;
if(tree[x<<1] >= hh) rdec(hh, lx, m, x<<1);
tree[x] = max(tree[x<<1], tree[(x<<1)+1]);
}
void rdecr(int hh){
dd.clear();
rdec(hh, 1, s, 1);
}
void ssin(int in, int lx, int rx, int x){
//cout<<lx<<" "<<rx<<" "<<in<<endl;
if(lx == rx){
tree[x]--;
return;
}int m = (lx + rx)>>1;
if(in <= m) ssin(in, lx, m, x*2);
else ssin(in, m+1, rx, x*2+1);
tree[x] = max(tree[x*2], tree[x*2+1]);
}
void subin(int in){
ssin(in, 1, s, 1);
}
void print(){
for(int i=1;i<2*s;i++) cout<<tree[i]<<" ";
cout<<endl;
}
};
void solve(){
cin>>n>>m>>rr>>k>>p;
aa.resize(n);
for(int i=0;i<n;i++){
aa[i].resize(m);
for(int j=0;j<m;j++) cin>>aa[i][j];
}
vector<TREE> row(n), col(m);
for(int i=0;i<n;i++) row[i].init(m, aa[i]);
for(int i=0;i<m;i++){
vii tmp(n);
for(int j=0;j<n;j++) tmp[j] = aa[j][i];
col[i].init(n, tmp);
}
for(int i=0;i<k;i++){
char dd;
cin>>dd;
if(dd == 'N'){
int in, hh;
cin>>in>>hh;
in--;
col[in].rr = rr;
col[in].decr(hh);
vii tmp = col[in].dd;
for(auto x:tmp) row[x-1].subin(in+1);
}else if(dd == 'S'){
int in, hh;
cin>>in>>hh;
in--;
col[in].rr = rr;
col[in].rdecr(hh);
vii tmp = col[in].dd;
for(auto x:tmp) row[x-1].subin(in+1);
}else if(dd == 'W'){
int in, hh;
cin>>in>>hh;
in--;
row[in].rr = rr;
row[in].decr(hh);
vii tmp = row[in].dd;
for(auto x:tmp) col[x-1].subin(in+1);
}else {
int in, hh;
cin>>in>>hh;
in--;
row[in].rr = rr;
row[in].rdecr(hh);
vii tmp = row[in].dd;
for(auto x:tmp) col[x-1].subin(in+1);
}
}
vector<vii> a(n), pp(n);
for(int i=0;i<n;i++){
pp[i].resize(m);
a[i].resize(m);
for(int j=0;j<m;j++) a[i][j] = row[i].tree[j+(row[i].s)];
}
vii r(n, 0), cc(m, 0);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i&&j) pp[i][j] += pp[i-1][j-1] + r[i] + cc[j] + a[i][j];
else if(i) pp[i][j] = cc[j] + a[i][j];
else if(j) pp[i][j] = r[i] + a[i][j];
else pp[i][j] = a[i][j];
r[i] += a[i][j];
cc[j] += a[i][j];
}
}
ans = 0;
for(int i=p-1;i<n;i++){
for(int j=p-1;j<m;j++){
if(i >= p && j >= p){
int tmp = pp[i][j] - pp[i-p][j] - pp[i][j-p] + pp[i-p][j-p];
umax(ans, tmp);
}else if(i == p-1 && j == p-1) umax(ans, pp[i][j]);
else if(i == p-1) umax(ans, pp[i][j] - pp[i][j-p]);
else if(j == p-1) umax(ans, pp[i][j] - pp[i-1][j]);
}
}
cout<<ans<<"\n";
return;
}
/*
4 8 2 6 2
1 1 1 1 1 1 1 1
1 2 3 1 1 1 3 1
1 2 1 1 3 1 1 1
1 1 1 1 1 1 1 2
N 2 2
W 2 2
W 2 3
S 2 1
S 4 1
S 7 1
*/
main(){
fastios
int t = 0;
if(!t) solve();
else {
cin>>t;
while (t--) solve();
}
}
Compilation message
ufo.cpp:219:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
219 | main(){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1132 KB |
Output is correct |
| 5 |
Correct |
70 ms |
5484 KB |
Output is correct |
| 6 |
Correct |
173 ms |
37868 KB |
Output is correct |
| 7 |
Correct |
274 ms |
83676 KB |
Output is correct |
| 8 |
Correct |
183 ms |
82520 KB |
Output is correct |
| 9 |
Correct |
308 ms |
78900 KB |
Output is correct |
| 10 |
Correct |
341 ms |
83100 KB |
Output is correct |
| 11 |
Correct |
243 ms |
68672 KB |
Output is correct |
| 12 |
Correct |
361 ms |
83164 KB |
Output is correct |
| 13 |
Correct |
491 ms |
96208 KB |
Output is correct |
| 14 |
Correct |
456 ms |
68928 KB |
Output is correct |
| 15 |
Correct |
580 ms |
83164 KB |
Output is correct |
| 16 |
Correct |
191 ms |
69728 KB |
Output is correct |
| 17 |
Correct |
936 ms |
97680 KB |
Output is correct |
| 18 |
Correct |
220 ms |
76064 KB |
Output is correct |
| 19 |
Correct |
263 ms |
91600 KB |
Output is correct |
| 20 |
Correct |
1042 ms |
162264 KB |
Output is correct |
