Editorial for Bedao Grand Contest 02 - ZENBEO


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define tag "ZENBEO"
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int m,n,k;
int a[407][407];
int c[407][407];
int cnt[26];

void enter(){
    cin>>m>>n>>k;

    char x;
    forinc(i,1,m) forinc(j,1,n) cin>>x,assert('a'<=x && x<='z'),c[i][j]=x-'a',a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(x=='z');
}

#define sum(x,y,u,v) (x<=u && y<=v ? a[u][v]-a[x-1][v]-a[u][y-1]+a[x-1][y-1] : 0)

void solve(){
    int64_t ans=0;

    forinc(x,1,m) forinc(u,x,m){
        memset(cnt,0,sizeof(cnt));

        for(int l=1,r=0;l<=n;l++){
            while(r<n && sum(x,l,u,r+1)<=k) cnt[c[x][++r]]+=c[x][r]==c[u][r];

            if(c[x][l]==c[u][l]) ans+=max(0,cnt[c[x][l]]--);
        }
    }

    cout<<ans<<"\n";
}

signed main(){
    checkfile(tag);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    enter();
    solve();

    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.