kt/D.cpp at main · dung195/kt · GitHub

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pq priority_queue
#define pii pair<ll,ll>
#define pll pair<ll,ll>
typedef vector<vector<ll> > vvi;
const ll sized=2207;
const ll inf=1e9+7;
ll mau[sized][sized];
int F[sized][sized];
int find(int n,int m){
    if(F[n][m]!=0) return F[n][m];
    if(n==0 || m==0) return 0;
    if(n==1 && m==1) return mau[n][m];
    else{
        if(n==1 || m==1 )
        F[n][m]=find(n,m-1)+find(n-1,m)+find(n-1,m-1)+mau[n][m]*(abs(n-1)+abs(m-1));

        else
        F[n][m]=find(n,m-1)+find(n-1,m)+find(n-1,m-1)+mau[n][m]*(abs(n-1)+abs(m-1)+1);
        return F[n][m];
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("main.inp","r",stdin);
    // freopen("main.out","w",stdout);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            mau[i][j+1]=s[j]-48;
        }
    }
    // find(n,m);
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         cout<<F[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    cout<<find(n,m)<<endl;
    return 0;
}