QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232041#7057. Digital PathRonbogo#WA 123ms29032kbC++202.1kb2023-10-29 19:29:152023-10-29 19:29:15

Judging History

你现在查看的是最新测评结果

  • [2023-10-29 19:29:15]
  • 评测
  • 测评结果:WA
  • 用时:123ms
  • 内存:29032kb
  • [2023-10-29 19:29:15]
  • 提交

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'