Submission #1182655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182655		bbartek	Sandcastle 2 (JOI22_ho_t5)	C++20	24 / 100	5092 ms	1864 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define st first
#define nd second
#define pb push_back

const int maxn = 5e4+7;

vector<int> tab[maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    int a;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a;
            tab[i].pb(a);
        }
    }

    ll wyn=0,ost,dlu;
    if(n==1){
        ost = 1e9;
        dlu = 0;
        for(int i=0;i<m;i++){
            if(tab[0][i] < ost){
                dlu++;
                wyn += dlu;
            }
            else{
                dlu = 1;
                wyn += dlu;
            }
            ost = tab[0][i];
        }
        ost = 1e9;
        dlu = 0;
        for(int i=m-1;i>=0;i--){
            if(tab[0][i] < ost){
                dlu++;
                wyn += dlu;
            }
            else{
                dlu = 1;
                wyn += dlu;
            }
            ost = tab[0][i];
        }
        wyn -= m;
        cout<<wyn<<"\n";
        return 0;
    }
    else{
        ll minimum,licznik=0,strona;
        pair<int,int> ind;
        bool czyok;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int i2=i;i2<n;i2++){
                    for(int j2=j;j2<m;j2++){
                        minimum = 1e9;
                        for(int i3=i;i3<=i2;i3++){
                            for(int j3=j;j3<=j2;j3++){
                                if(tab[i3][j3] < minimum){
                                    minimum = tab[i3][j3];
                                    ind = {i3,j3};
                                }
                            }
                        }
                        czyok = 1;
                        licznik = 1;
                        while(licznik < (i2-i+1)*(j2-j+1)){
                            minimum = 1e9;
                            if(ind.st + 1 <= i2 && minimum > tab[ind.st+1][ind.nd] && tab[ind.st][ind.nd] < tab[ind.st+1][ind.nd]){
                                minimum = tab[ind.st+1][ind.nd];
                                strona = 1;
                            }
                            if(ind.nd + 1 <= j2 && minimum > tab[ind.st][ind.nd+1] && tab[ind.st][ind.nd] < tab[ind.st][ind.nd+1]){
                                minimum = tab[ind.st][ind.nd+1];
                                strona = 2;
                            }
                            if(ind.st - 1 >= i && minimum > tab[ind.st-1][ind.nd] && tab[ind.st][ind.nd] < tab[ind.st-1][ind.nd]){
                                minimum = tab[ind.st-1][ind.nd];
                                strona = 3;
                            }
                            if(ind.nd - 1 >= j && minimum > tab[ind.st][ind.nd-1] && tab[ind.st][ind.nd] < tab[ind.st][ind.nd-1]){
                                minimum = tab[ind.st][ind.nd-1];
                                strona = 4;
                            }

                            if(minimum == 1e9 || minimum < tab[ind.st][ind.nd]){
                                czyok = 0;
                                break;
                            }
                            if(strona == 1)
                                ind.st++;
                            else if(strona == 2)
                                ind.nd++;
                            else if(strona == 3)
                                ind.st--;
                            else
                                ind.nd--;

                            licznik++;
                        }
                        if(czyok){
                            wyn++;
                        }
                    }
                }
            }
        }
        cout<<wyn<<"\n";
    }

    return 0;
}

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