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

Code

#include <bits/stdc++.h>
using namespace std;
const int M=1000000007;
int n;
int t[101][101];
long long w[101][101];
long long a[101][101];
int main(){
cin >> n;
for (int i=0;i<n;++i){
for (int j=0;j<n;++j){
cin >> t[i][j];
}
}
w[0][0]=1;
for (int i=0;i<n;++i){
for (int j=0;j<n;++j){
if (i) w[i][j]+=w[i-1][j];
if (w[i][j]>M) w[i][j]-=M;
if (j) w[i][j]+=w[i][j-1];
if (w[i][j]>M) w[i][j]-=M;
a[i][j]=t[i][j]*w[i][j]%M;
if (i) a[i][j]+=a[i-1][j];
if (a[i][j]>M) a[i][j]-=M;
if (j) a[i][j]+=a[i][j-1];
if (a[i][j]>M) a[i][j]-=M;
}
}
cout << a[n-1][n-1] << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
100
606755118 96655535 664126532 4...

correct output
530182530

user output
530182530