Submission #2119231
Source Code Expand
#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 | AC |
Exec Time | 525 ms |
Memory | 23680 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample01.txt, sample02.txt |
All | 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 | AC | 348 ms | 23680 KB |
01.txt | AC | 366 ms | 23552 KB |
02.txt | AC | 256 ms | 23680 KB |
03.txt | AC | 2 ms | 2304 KB |
04.txt | AC | 2 ms | 2304 KB |
05.txt | AC | 2 ms | 2304 KB |
06.txt | AC | 2 ms | 2304 KB |
07.txt | AC | 2 ms | 2304 KB |
08.txt | AC | 2 ms | 2432 KB |
09.txt | AC | 2 ms | 2304 KB |
10.txt | AC | 3 ms | 2560 KB |
11.txt | AC | 525 ms | 23680 KB |
12.txt | AC | 524 ms | 23680 KB |
13.txt | AC | 525 ms | 23680 KB |
14.txt | AC | 525 ms | 23680 KB |
15.txt | AC | 467 ms | 23680 KB |
16.txt | AC | 525 ms | 23680 KB |
17.txt | AC | 523 ms | 23680 KB |
18.txt | AC | 278 ms | 23680 KB |
19.txt | AC | 217 ms | 23680 KB |
sample01.txt | AC | 2 ms | 2304 KB |
sample02.txt | AC | 2 ms | 2304 KB |