oj.uz

Submission #144110

# Submission time Handle Problem Language Result Execution time Memory
144110 2019-08-16T05:36:43 Z Abelyan UFO (IZhO14_ufo) C++17
100 / 100
 1053 ms 149752 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 94328 KB Output is correct
2 Correct 88 ms 94328 KB Output is correct
3 Correct 90 ms 94328 KB Output is correct
4 Correct 107 ms 94840 KB Output is correct
5 Correct 179 ms 96760 KB Output is correct
6 Correct 292 ms 114896 KB Output is correct
7 Correct 396 ms 139052 KB Output is correct
8 Correct 290 ms 135544 KB Output is correct
9 Correct 450 ms 133880 KB Output is correct
10 Correct 480 ms 134648 KB Output is correct
11 Correct 381 ms 133236 KB Output is correct
12 Correct 499 ms 134660 KB Output is correct
13 Correct 613 ms 138616 KB Output is correct
14 Correct 589 ms 133368 KB Output is correct
15 Correct 684 ms 136312 KB Output is correct
16 Correct 305 ms 135512 KB Output is correct
17 Correct 1053 ms 143160 KB Output is correct
18 Correct 324 ms 136440 KB Output is correct
19 Correct 363 ms 137720 KB Output is correct
20 Correct 1010 ms 149752 KB Output is correct