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
#include "dzialka.h"
#include "message.h"
#include<iostream>
#include<vector>
using namespace std;
long long akt[75001];
long long gl[75001];
long long dp[75001];
long long mniejszy[75001];
long long wynik;
long long roz;
int instancje,id,y,x,sz;
vector<pair<int,int>>v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    instancje=NumberOfNodes();
    id=MyNodeId();
    if(id!=0)return 0;
    y=GetFieldHeight();
    x=GetFieldWidth();
    for(int i=0;i<y;++i){
        for(int j=0;j<x;++j){
            akt[j]=IsUsableCell(i,j);
            if(akt[j]==1){
                ++gl[j];
            }
            else{
                gl[j]=0;
            }
        }
        v.resize(0);
        for(int j=0;j<x;++j){
            while(v.size()>0&&v.back().second>=gl[j]){
                v.pop_back();
            }
            if(v.size()==0){
                mniejszy[j]=-1;
            }
            else{
                mniejszy[j]=v.back().first;
            }
            v.push_back(make_pair(j,gl[j]));
        }
        for(int j=0;j<x;++j){
            if(mniejszy[j]==-1){
                roz=j+1;
                dp[j]=roz*gl[j];
                wynik+=dp[j];
            }
            else{
                roz=j-mniejszy[j];
                dp[j]=dp[mniejszy[j]]+roz*gl[j];
                wynik+=dp[j];
            }
        }
    }
    cout<<wynik;
}