QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640235#7057. Digital PathLoxilante#WA 331ms162420kbC++141.8kb2024-10-14 09:47:532024-10-14 09:47:53

Judging History

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

  • [2024-10-14 09:47:53]
  • 评测
  • 测评结果:WA
  • 用时:331ms
  • 内存:162420kb
  • [2024-10-14 09:47:53]
  • 提交

answer

#define F_C
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; i++)
#define hrp(i, l, r) for(int i = l; i <= r; i++)
#define rev(i, r, l) for(int i = r; i >= l; i--)
#define int ll
using namespace std;
typedef long long ll;
template<typename tn = int> tn next(void) { tn k; cin>>k; return k; }
#ifndef LOCAL
#define D(...) 0
#endif
const int U = 1500;
const int MOD = 1000000007;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int dp1[U][U][5], dp2[U][U], w[U][U];
map<int, vector<pair<int, int>>> pos;
signed main(void)
{
    #ifdef LOCAL
//	freopen("C:\\Users\\Loxil\\Desktop\\IN.txt", "r", stdin);
//	freopen("C:\\Users\\Loxil\\Desktop\\OUT.txt", "w", stdout);
    #endif
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    set<int> uni;
    cin>>n>>m;
    hrp(i, 1, n) hrp(j, 1, m) cin>>w[i][j], uni.insert(w[i][j]), pos[w[i][j]].push_back({i, j});
    hrp(i, 1, n) hrp(j, 1, m)
    {
        bool ext = 0;
        rep(d, 0, 4)
        {
            int x = i+dx[d], y = j+dy[d];
            if (1 <= x && x <= n && 1 <= y && y <= m && w[x][y] == w[i][j]-1) ext = 1;
        }
        dp1[i][j][0] = !ext;
    }

    for(auto v: uni) for(auto p: pos[v]) rep(d, 0, 4) 
    {
        int i = p.first, j = p.second, x = i+dx[d], y = j+dy[d];

        if (w[x][y] == v+1) hrp(k, 1, 4)
            dp1[x][y][min(3LL, k)] += dp1[i][j][k-1];
    }

    int ans = 0;
    hrp(i, 1, n) hrp(j, 1, m)
    {
        bool ext = 0;
        rep(d, 0, 4)
        {
            int x = i+dx[d], y = j+dy[d];
            if (1 <= x && x <= n && 1 <= y && y <= m && w[x][y] == w[i][j]+1) ext = 1;
        }
        if (!ext) ans += dp1[i][j][3];
        ans %= MOD;
    }
    cout<<ans<<endl;
        
    return 0;
}
/*
5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5876kb

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: 1ms
memory: 5688kb

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: 331ms
memory: 162420kb

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:

615609262

result:

wrong answer 1st lines differ - expected: '990039586', found: '615609262'