1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <vector>
#include "message.h"
#include "dzialka.h"
using namespace std;

long long n,m;
long long prefL[2137][2137];//[n][m]
long long wyn[2137][2137];//[n][m]
struct node{
    long long pos;
    long long war;
    node(long long pos,long long war){
        this->pos = pos;
        this->war = war;
    }
    node(){

    }
};
int main(){
    if (MyNodeId() > 0)
        return 0;

    n = GetFieldHeight();
    m = GetFieldWidth();
    //scanf("%lld%lld",&n,&m);
    for(long long i=1; i<=n; i++){
        for(long long j=1; j<=m; j++){
            prefL[i][j] = IsUsableCell(i-1,j-1);
        }
    }
    for(long long i=1; i<=n; i++){
        for(long long j=1; j<=m; j++){
            if(prefL[i][j]!=0){
                prefL[i][j] = prefL[i][j-1]+1;
            }
            //printf("%d ",prefL[i][j]);
        }
        //printf("\n");
    }
    for(long long j=1; j<=m; j++){
        vector<node> v;
        long long iloczyncz = 0;//ilewartosci = v.size();
        for(long long i=1; i<=n; i++){
            long long prefwar = prefL[i][j];
            if(prefwar == 0){
                v.clear();
                iloczyncz = 0;
            }
            else{
                long long tmppos = i;
                //long long odjete = 0;
                while(v.size()>0 and v[v.size()-1].war>prefwar){
                    //printf("v[v.size()-1].war: %d prefwar: %d\n",v[v.size()-1].war,prefwar);
                    long long tmpwar = prefwar;
                    if(v.size()-1>0){
                        tmpwar = max(prefwar,v[v.size()-2].war);
                    }
                    
                    iloczyncz-=(v[v.size()-1].war-tmpwar)*(i-v[v.size()-1].pos);
                    //odjete+=(v[v.size()-1].war-tmpwar)*(i-v[v.size()-1].pos);
                    if(v[v.size()-1].pos<tmppos){
                        tmppos = v[v.size()-1].pos;
                    }
                    v.pop_back();
                }
                iloczyncz+=prefwar;

                if(v.size()==0){
                    v.push_back(node(tmppos,prefwar));
                }
                else if(v[v.size()-1].war < prefwar){
                    v.push_back(node(tmppos,prefwar));
                }
                
                wyn[i][j] = iloczyncz;
                //if(j==6){
                //  printf("i: %d v.size(): %d odjete: %d tmppos: %d\n",i,v.size(),odjete,tmppos);
                //}
            }

        }
    }
    long long wynik = 0;
    
    for(long long i=1; i<=n; i++){
        for(long long j=1; j<=m; j++){
            wynik+=wyn[i][j];
    //      printf("%d ",wyn[i][j]);
        }
    //  printf("\n");
    }
    printf("%lld",wynik);
}