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