CSES - HIIT Open 2019 - Results
Submission details
Task:Grid Paths
Sender:Game of Nolife
Submission time:2019-05-25 11:07:13 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.03 sdetails

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

ll m[111][111];

ll mod=1e9+7;

ll ps[111][111];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for (int i=0;i<n;i++){
        for (int ii=0;ii<n;ii++){
            cin>>m[i][ii];
        }
    }
    ps[0][0]=1;
    for (int i=0;i<n;i++){
        for (int ii=0;ii<n;ii++){
            if (i>0) ps[i][ii]+=ps[i-1][ii];
            if (ii>0) ps[i][ii]+=ps[i][ii-1];
            ps[i][ii]%=mod;
        }
    }
    ll ans=0;
    for (int i=0;i<n;i++){
        for (int ii=0;ii<n;ii++){
            ll tp=ps[i][ii]*ps[n-i-1][n-ii-1];
            tp%=mod;
            ans+=tp*m[i][ii];
            ans%=mod;
        }
    }
    cout<<ans<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
100
606755118 96655535 664126532 4...

correct output
530182530

user output
530182530