Submission #144110

#	Time	Username	Problem	Language	Result	Execution time	Memory
144110		Abelyan	UFO (IZhO14_ufo)	C++17	100 / 100	1053 ms	149752 KiB

ufo

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=2e6+10;
const ll MOD=998244353;
 
 
vector<int> segs[N],segt[N];
 
vector<vector<int> > a;
 
void build(vector<int> &sg,int v,int tl,int tr,int ham,bool tox){
    if (tl==tr){
        if (tox) sg[v]=(a[ham][tl]);
        else sg[v]=(a[tl][ham]);
        return;
    }
    int tm=(tl+tr)/2;
    build(sg,v+v,tl,tm,ham,tox);
    build(sg,v+v+1,tm+1,tr,ham,tox);
    sg[v]=sg[v+v]+sg[v+v+1];
}
 
void update(vector<int> &sg,int v,int tl,int tr,int ind,int val){
    //cout<<v<<" "<<tl<<" "<<tr<<" "<<ind<<" "<<val<<endl;
    if (tl==tr){
        sg[v]=val;
        //cout<<"hey "<<tl<<" "<<val<<endl;
        //cout<<sg[v].mx<<endl;
        return;
    }
    int tm=(tl+tr)/2;
    if (ind<=tm)update(sg,v+v,tl,tm,ind,val);
    else update(sg,v+v+1,tm+1,tr,ind,val);
    sg[v]=max(sg[v+v],sg[v+v+1]);
}
 
vector<int> pox;
 
int query(vector<int> &sg,int v,int tl,int tr,int val,int qan,bool norm){
    if (!qan || sg[v]<val)return qan;
    //cout<<v<<" "<<tl<<" "<<tr<<" "<<sg[v]<<" "<<val<<" "<<qan<<endl;
    if (tl==tr){
        //cout<<tl<<" "<<sg[v]<<" "<<val<<endl;
        if (sg[v]>=val){
            pox.ad(tl);
            sg[v]--;
            return qan-1;
        }
        return qan;
    }
    //cout<<sg[v].mx<<" "<<tl<<" "<<tr<<" "<<qan<<" asdfadf"<<endl;;
    if (sg[v]<val)return qan;
    int tm=(tl+tr)/2;
    //cout<<sg[v].mx<<" "<<tl<<" "<<tr<<" "<<qan<<" asdfadf"<<endl;;
    if (norm){
        if (sg[v+v]>=val) qan=query(sg,v+v,tl,tm,val,qan,norm);
        if (sg[v+v+1]>=val)qan=query(sg,v+v+1,tm+1,tr,val,qan,norm);
    }
    else{
 
        if (sg[v+v+1]>=val)qan=query(sg,v+v+1,tm+1,tr,val,qan,norm);
        if (sg[v+v]>=val) qan=query(sg,v+v,tl,tm,val,qan,norm);
    }
    sg[v]=max(sg[v+v],sg[v+v+1]);
 
    return qan;
}
 
int n,m,r,k,p;
void upd(int ham,bool tox,bool norm,int val){
    pox.clear();
    if (tox){
        query(segt[ham],1,0,m-1,val,r,norm);
        trav(tv,pox){
            //cout<<tv<<endl;
            a[ham][tv]--;
            update(segs[tv],1,0,n-1,ham,a[ham][tv]);
        }
    }
    else{
        query(segs[ham],1,0,n-1,val,r,norm);
        trav(tv,pox){
            //cout<<tv<<endl;
            a[tv][ham]--;
            update(segt[tv],1,0,m-1,ham,a[tv][ham]);
        }
    }
}
 
int main(){
    fastio;
    srng;
    //freopen("c.in","r",stdin);
    cin>>n>>m>>r>>k>>p;
    a.resize(n);
    FOR(i,n){
        a[i].resize(m);
        FOR(j,m)cin>>a[i][j];
        segt[i].resize(4*m);
        build(segt[i],1,0,m-1,i,true);
    }
    FOR(i,m){
        segs[i].resize(4*n);
        build(segs[i],1,0,n-1,i,false);
    }
    FOR(tt,k){
        char c;
        int ham,bdz;
        cin>>c>>ham>>bdz;
        ham--;
        if (c=='W')upd(ham,true,true,bdz);
        if (c=='E')upd(ham,true,false,bdz);
        if (c=='N')upd(ham,false,true,bdz);
        if (c=='S')upd(ham,false,false,bdz);
        /*
        FOR(i,n){
        FOR(j,m){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
        }*/
    }
    /*
    FOR(i,n){
    FOR(j,m){
        cout<<a[i][j]<<" ";
    }
    cout<<endl;
    }*/
    int ans=0;
    FOR(i,n-p+1){
        FOR(j,m-p+1){
            int qan=0;
            FORT(i1,i,i+p-1)FORT(j1,j,j+p-1)qan+=a[i1][j1];
 
            //cout<<i<<" "<<j<<" "<<qan<<endl;
            ans=max(ans,qan);
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*
7 2 8
C 1
C 2
C 3
C 4
C 5
C 6
O 7
O 7
 
*/

• Subtask 1: 100 / 100