Submission #2119231


Source Code Expand

Copy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int v[1000][1000];
ll sum[1000][1000]={};

int main(void) {
  int i,j;
  int h,w;
  cin>>h>>w;
  vector< pair<int,pii> > p(h*w);
  rep(i,h)rep(j,w){
    cin>>v[i][j];
    p[i*w+j].first=v[i][j];
    p[i*w+j].second.first=i;
    p[i*w+j].second.second=j;
  }
  sort(all(p));
  int dx[4]={0,1,0,-1};
  int dy[4]={1,0,-1,0};
  int n=h*w;
  rep(i,n){
    int x=p[n-1-i].second.first;
    int y=p[n-1-i].second.second;
    sum[x][y]++;
    rep(j,4){
      int nx=x+dx[j];
      int ny=y+dy[j];
      if(nx<0 || nx>=h || ny<0 || ny>=w)continue;
      if(v[x][y]<v[nx][ny])sum[x][y]=(sum[x][y]+sum[nx][ny])%MOD;
    }
  }
  ll ans=0;
  rep(i,h)rep(j,w)ans=(ans+sum[i][j])%MOD;
  cout<<ans<<endl;
}

Submission Info

Submission Time
Task D - 経路
User rika0384
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1365 Byte
Status
Exec Time 525 ms
Memory 23680 KB

Test Cases

Set Name Score / Max Score Test Cases
sample 0 / 0 sample01.txt, sample02.txt
All 100 / 100 00.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, sample01.txt, sample02.txt, sample01.txt, sample02.txt
Case Name Status Exec Time Memory
00.txt 348 ms 23680 KB
01.txt 366 ms 23552 KB
02.txt 256 ms 23680 KB
03.txt 2 ms 2304 KB
04.txt 2 ms 2304 KB
05.txt 2 ms 2304 KB
06.txt 2 ms 2304 KB
07.txt 2 ms 2304 KB
08.txt 2 ms 2432 KB
09.txt 2 ms 2304 KB
10.txt 3 ms 2560 KB
11.txt 525 ms 23680 KB
12.txt 524 ms 23680 KB
13.txt 525 ms 23680 KB
14.txt 525 ms 23680 KB
15.txt 467 ms 23680 KB
16.txt 525 ms 23680 KB
17.txt 523 ms 23680 KB
18.txt 278 ms 23680 KB
19.txt 217 ms 23680 KB
sample01.txt 2 ms 2304 KB
sample02.txt 2 ms 2304 KB