Submission #1186145

#TimeUsernameProblemLanguageResultExecution timeMemory
1186145PieArmyUFO (IZhO14_ufo)C++20
95 / 100
622 ms195988 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' #define mid ((left+right)>>1) using namespace std; struct Seg{ int n; vector<ll>tree,arr; void build(int node=1,int left=0,int right=-1){ if(right==-1)right=n-1; if(left==right){ tree[node]=arr[left]; return; } build(node*2,left,mid); build(node*2+1,mid+1,right); tree[node]=max(tree[node*2],tree[node*2+1]); } void init(vector<ll>Arr){ arr=Arr; n=arr.size(); tree.resize(n<<2,0); build(); } int x; void up(int node=1,int left=0,int right=-1){ if(right==-1)right=n-1; if(left==right){ tree[node]--; return; } if(x>mid)up(node*2+1,mid+1,right); else up(node*2,left,mid); tree[node]=max(tree[node*2],tree[node*2+1]); } void update(int tar){ x=tar; up(); } int walk1(int val,int loc,int node=1,int left=0,int right=-1){ if(tree[node]<val)return n; if(right==-1)right=n-1; if(right<loc)return n; if(left==right)return left; int res=walk1(val,loc,node*2,left,mid); if(res==n)return walk1(val,loc,node*2+1,mid+1,right); return res; } int walk2(int val,int loc,int node=1,int left=0,int right=-1){ if(tree[node]<val)return -1; if(right==-1)right=n-1; if(left>loc)return -1; if(left==right)return left; int res=walk2(val,loc,node*2+1,mid+1,right); if(res==-1)return walk2(val,loc,node*2,left,mid); return res; } void dfs(int node=1,int left=0,int right=-1){ if(right==-1)right=n-1; if(left==right){ arr[left]=tree[node]; return; } dfs(node*2,left,mid); dfs(node*2+1,mid+1,right); } vector<ll> getvals(){ dfs(); return arr; } }; int n,m,r,k,p; vector<vector<ll>>mat; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>m>>r>>k>>p; mat.resize(n,vector<ll>(m)); Seg row[n],col[m]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>mat[i][j]; } row[i].init(mat[i]); } for(int i=0;i<m;i++){ vector<ll>v; for(int j=0;j<n;j++){ v.pb(mat[j][i]); } col[i].init(v); } for(int i=0;i<k;i++){ char c;cin>>c; int x,h;cin>>x>>h; x--; if(c=='N'){ int s=r; int pos=0; while(s&&pos!=n){ pos=col[x].walk1(h,pos); if(pos==n)break; col[x].update(pos); row[pos].update(x); pos++; s--; } } if(c=='S'){ int s=r; int pos=n-1; while(s&&pos!=-1){ pos=col[x].walk2(h,pos); if(pos==-1)break; col[x].update(pos); row[pos].update(x); pos--; s--; } } if(c=='W'){ int s=r; int pos=0; while(s&&pos!=m){ pos=row[x].walk1(h,pos); if(pos==m)break; row[x].update(pos); col[pos].update(x); pos++; s--; } } if(c=='E'){ int s=r; int pos=m-1; while(s&&pos!=-1){ pos=row[x].walk2(h,pos); if(pos==-1)break; row[x].update(pos); col[pos].update(x); pos--; s--; } } } for(int i=0;i<n;i++){ mat[i]=row[i].getvals(); for(int j=1;j<m;j++){ mat[i][j]+=mat[i][j-1]; if(i){ mat[i][j]+=mat[i-1][j]-mat[i-1][j-1]; } } } ll ans=0; if(p==0){ cout<<"0\n"; return 0; } for(int i=p-1;i<n;i++){ for(int j=p-1;j<m;j++){ ll sum=mat[i][j]; if(i-p>=0){ sum-=mat[i-p][j]; } if(j-p>=0){ sum-=mat[i][j-p]; } if(i-p>=0&&j-p>=0){ sum+=mat[i-p][j-p]; } ans=max(ans,sum); } } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...