oj.uz

Submission #1067155

# Submission time Handle Problem Language Result Execution time Memory
1067155 2024-08-20T12:09:08 Z Unforgettablepl Abduction 2 (JOI17_abduction2) C++17
13 / 100
 5000 ms 98956 KB 
#pragma GCC optimize("Ofast","unroll-all-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int H,W,Q;
    cin >> H >> W >> Q;
    vector<int> A(H+1);
    for(int i=1;i<=H;i++)cin>>A[i];
    vector<int> B(W+1);
    for(int i=1;i<=W;i++)cin>>B[i];
    vector visited(5,vector(H+1,vector(W+1,-1)));
    for(int i=1;i<=Q;i++) {
        int s,t;
        cin>>s>>t;
        int bestans = 0;
        function<int(int,int,int&,int&)> dfs = [&](int x,int y, const int &parx, const int &pary) {
            if(x<1 or x>H or y<1 or y>W)return -1;
            int pedge = 0;
            if(x>parx)pedge=1;
            else if(x<parx)pedge=2;
            else if(y>pary)pedge=3;
            else if(y<pary)pedge=4;
            // if(visited[pedge][x][y]!=-1)return visited[pedge][x][y];
            int ans=0;
            if(A[x]>B[y]) {
                if(x!=parx or y-1!=pary)ans=max(dfs(x,y-1,x,y)+1,ans);
                if(x!=parx or y+1!=pary)ans=max(dfs(x,y+1,x,y)+1,ans);
            } else {
                if(x+1!=parx or y!=pary)ans=max(dfs(x+1,y,x,y)+1,ans);
                if(x-1!=parx or y!=pary)ans=max(dfs(x-1,y,x,y)+1,ans);
            }
            return visited[pedge][x][y]=ans;
        };
        bestans = max(bestans,dfs(s,t,s,t));
        if(A[s]>B[t]) {
            bestans=max(bestans,dfs(s-1,t,s,t)+1);
            bestans=max(bestans,dfs(s+1,t,s,t)+1);
        } else {
            bestans=max(bestans,dfs(s,t-1,s,t)+1);
            bestans=max(bestans,dfs(s,t+1,s,t)+1);
        }
        cout << bestans << '\n';
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 54 ms 95072 KB Output is correct
13 Correct 48 ms 95060 KB Output is correct
14 Correct 41 ms 95136 KB Output is correct
15 Correct 39 ms 95116 KB Output is correct
16 Correct 52 ms 95056 KB Output is correct
17 Correct 41 ms 95064 KB Output is correct
18 Correct 62 ms 95176 KB Output is correct
19 Execution timed out 5042 ms 98956 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 54 ms 95072 KB Output is correct
13 Correct 48 ms 95060 KB Output is correct
14 Correct 41 ms 95136 KB Output is correct
15 Correct 39 ms 95116 KB Output is correct
16 Correct 52 ms 95056 KB Output is correct
17 Correct 41 ms 95064 KB Output is correct
18 Correct 62 ms 95176 KB Output is correct
19 Execution timed out 5042 ms 98956 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4810 ms 95456 KB Output is correct
2 Correct 2581 ms 95256 KB Output is correct
3 Correct 3514 ms 95312 KB Output is correct
4 Correct 3801 ms 95436 KB Output is correct
5 Execution timed out 5078 ms 95316 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 54 ms 95072 KB Output is correct
13 Correct 48 ms 95060 KB Output is correct
14 Correct 41 ms 95136 KB Output is correct
15 Correct 39 ms 95116 KB Output is correct
16 Correct 52 ms 95056 KB Output is correct
17 Correct 41 ms 95064 KB Output is correct
18 Correct 62 ms 95176 KB Output is correct
19 Execution timed out 5042 ms 98956 KB Time limit exceeded
20 Halted 0 ms 0 KB -