QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#232041 | #7057. Digital Path | Ronbogo# | WA | 123ms | 29032kb | C++20 | 2.1kb | 2023-10-29 19:29:15 | 2023-10-29 19:29:15 |
Judging History
answer
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#define INF 0x3f3f3f3f
#define debug(x) std::cout<<#x<<":"<<x<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const int N=1e6;
const int P = 1e9 + 7;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
signed main() {
#ifndef ONLINE_JUDGE
freopen("/Users/holden/Desktop/code/cin.in", "r", stdin);
freopen("/Users/holden/Desktop/code/cout.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n,vector<int>(m));
vector<vector<ll>> dp(n,vector<ll>(m, 0));
vector<vector<bool>> f(n, vector<bool>(m));
vector<pair<int, pii>> v;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> g[i][j];
v.push_back({g[i][j], {i, j}});
}
}
sort(v.begin(), v.end());
for (auto it : v) {
if (it.first == 1) {
f[it.second.first][it.second.second] = true;
dp[it.second.first][it.second.second] = 1;
}
bool ff = false;
for (int i = 0; i < 4; ++i) {
int x = it.second.first + dx[i];
int y = it.second.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y]-1 == g[it.second.first][it.second.second]) {
ff = true;
f[x][y] = true;
dp[x][y] = (dp[it.second.first][it.second.second] + dp[x][y]) % P;
}
}
if (ff) {
f[it.second.first][it.second.second] = false;
}
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (g[i][j] >= 4 && f[i][j]) {
ans = (ans + dp[i][j]) % P;
ans %= P;
}
}
}
cout << ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3388kb
input:
3 5 1 2 3 8 7 -1 -1 4 5 6 1 2 3 8 7
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3420kb
input:
4 4 1 2 3 4 2 3 4 3 3 4 3 2 4 3 2 1
output:
16
result:
ok single line: '16'
Test #3:
score: -100
Wrong Answer
time: 123ms
memory: 29032kb
input:
1000 1000 1000000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 ...
output:
0
result:
wrong answer 1st lines differ - expected: '990039586', found: '0'