Submission #1188889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188889		user736482	Sandcastle 2 (JOI22_ho_t5)	C++20	15 / 100	5094 ms	64708 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,r,c,t,n,m,l,q,k,ak,ans,s,h,w;

vector<vector<ll>>in,pref[81];
vector<pair<ll,ll>>sas={{0,1},{1,0},{0,-1},{-1,0}};


ll czy(ll i,ll j,ll k){
    ll l=max(-(k%3),-j);k/=3;
    ll p=min((k%3),w-j-1);k/=3;
    ll g=max(-(k%3),-i);k/=3;
    ll d=min(k%3,h-i-1);
   // cout<<i<<" "<<j<<" "<<g<<" "<<d<<" "<<l<<" "<<p<<"\n"<<flush;
    ll ile=0;
    bool czy=0;
    for(auto x : sas){
        if(x.ff>=g && x.ff<=d && x.ss>=l && x.ss<=p){
            if(in[x.ff+i][x.ss+j]<in[i][j])czy=1;
            ll mx=-1;
            for(auto o : sas ){
                pair<ll,ll> y={x.ff+o.ff,x.ss+o.ss};  
                
                if(y.ff>=g && y.ff<=d && y.ss>=l && y.ss<=p){
                    if(in[y.ff+i][y.ss+j]<in[x.ff+i][x.ss+j])
                    mx=max(mx,in[y.ff+i][y.ss+j]);
                }
            }
            if(mx==in[i][j])ile++;
        }
    }
    return (!czy)+(ile!=1);
}

ll zle(ll i1,ll i2,ll j1,ll j2){
    ll cnt=0;
    for(ll i=0;i<81;i++){
        ll k=i;
        ll d=(k%3);k/=3;
        ll g=(k%3);k/=3;
        ll p=(k%3);k/=3;
        ll l=(k%3);
        ll pf=i2,lf=i1,df=j2,gf=j1;
        if(p==0){
            lf=max(i1,lf);
            pf=min(pf,i1);
        }
        else if(p==1){
            lf=max(i1+1,lf);
            pf=min(pf,i1+1);
        }
        else lf=max(i1+2,lf);
        
        
        if(l==0){
            lf=max(i2,lf);
            pf=min(pf,i2);
        }
        else if(l==1){
            lf=max(i2-1,lf);
            pf=min(pf,i2-1);
        }
        else pf=min(i2-2,pf);
        
        
        
        if(d==0){
            gf=max(j1,gf);
            df=min(df,j1);
        }
        else if(d==1){
            gf=max(j1+1,gf);
            df=min(df,j1+1);
        }
        else gf=max(j1+2,gf);
        
        
        if(g==0){
            gf=max(j2,gf);
            df=min(df,j2);
        }
        else if(g==1){
            gf=max(j2-1,gf);
            df=min(df,j2-1);
        }
        else df=min(j2-2,df);
        
        
        
        
        //cout<<i1<<" "<<i2<<" "<<j1<<" "<<j2<<"xd"<<flush;
        if(lf<=pf && gf<=df){
            cnt+=(pref[i][pf+1][df+1]-pref[i][lf][df+1]-pref[i][pf+1][gf]+pref[i][lf][gf]);
            
        }
       // cout<<lf<<" "<<pf<<" "<<gf<<" "<<df<<"\n"<<flush;
        //cout<<"xd"<<flush;
    }
  //  cout<<"\n"<<cnt<<"\n\n";
    return cnt;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>h>>w;
    for(ll i=0;i<h;i++){
        in.pb({});
        for(ll j=0;j<w;j++){
            cin>>a;
            in.back().pb(a);
        }

    }//return 0;
    for(ll i=0;i<81;i++){
        pref[i].pb({});
        for(ll j=0;j<w;j++){
            pref[i].back().pb(0);
        }
        for(ll j=0;j<h;j++)pref[i].pb({0});
    }//return 0;
    for(ll i=0;i<81;i++){
        for(ll j=1;j<=h;j++){
            for(ll k=1;k<=w;k++){
                pref[i][j].pb(pref[i][j-1][k]+pref[i][j][k-1]-pref[i][j-1][k-1]+czy(j-1,k-1,i));
                //cout<<pref[i][j].back()<<" ";
            }
        ///    cout<<"\n";
        }
       // cout<<"\n";
    }
    
    for(ll i=0;i<h;i++){
        for(ll j=i;j<h;j++){
            for(ll k=0;k<w;k++){
                for(ll p=k;p<w;p++){
                    if(zle(i,j,k,p)==2)ans++;
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20