oj.uz

Submission #128618

# Submission time Handle Problem Language Result Execution time Memory
128618 2019-07-11T07:37:14 Z Utaha Abduction 2 (JOI17_abduction2) C++14
27 / 100
 369 ms 63868 KB 
/*input
4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<'('<<P.F<<','<<P.S<<')';
    return out;
}

//}}}
const ll maxn=2005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        
        b>>=1;
    }
    return res;
}

pii operator+(pii A,pii B){return MP(A.F+B.F,A.S+B.S);}

const pii dir[]={{0,1},{-1,0},{0,-1},{1,0}};

int n,m;
int r[maxn],c[maxn];
int dp[4][maxn][maxn];

int go(int idx,int x,int y){
    if(dp[idx][x][y]!=-1) return dp[idx][x][y];
    int destX=x+dir[idx].F;
    int destY=y+dir[idx].S;
    if(destX<0||destX>=n||destY<0||destY>=m) return dp[idx][x][y]=0;
    if(idx&1){ // x movement;
        if(c[y]>r[destX]) return dp[idx][x][y]=go(idx,destX,destY)+1;
        else{
            return dp[idx][x][y]=max(go(0,destX,destY),go(2,destX,destY))+1;
        }
    }
    else{
        if(r[x]>c[destY]) return dp[idx][x][y]=go(idx,destX,destY)+1;
        else{
            return dp[idx][x][y]=max(go(1,destX,destY),go(3,destX,destY))+1;
        }
    }
}

int main(){
    IOS;   
    int q;
    cin>>n>>m>>q;
    REP(i,n) cin>>r[i];
    REP(i,m) cin>>c[i];
    REP(i,4) REP(j,n) REP(k,m){
        dp[i][j][k]=-1;
    }
    REP(i,4) REP(j,n) REP(k,m){
        if(dp[i][j][k]==-1) go(i,j,k);
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        x--;y--;
        int ans=0;
        REP(i,4) ans=max(ans,dp[i][x][y]);
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 360 ms 63352 KB Output is correct
13 Correct 360 ms 63480 KB Output is correct
14 Correct 363 ms 63536 KB Output is correct
15 Correct 364 ms 63608 KB Output is correct
16 Correct 364 ms 63352 KB Output is correct
17 Correct 283 ms 63612 KB Output is correct
18 Correct 283 ms 63608 KB Output is correct
19 Correct 306 ms 63736 KB Output is correct
20 Correct 301 ms 61816 KB Output is correct
21 Correct 304 ms 63868 KB Output is correct
22 Correct 322 ms 63864 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 360 ms 63352 KB Output is correct
13 Correct 360 ms 63480 KB Output is correct
14 Correct 363 ms 63536 KB Output is correct
15 Correct 364 ms 63608 KB Output is correct
16 Correct 364 ms 63352 KB Output is correct
17 Correct 283 ms 63612 KB Output is correct
18 Correct 283 ms 63608 KB Output is correct
19 Correct 306 ms 63736 KB Output is correct
20 Correct 301 ms 61816 KB Output is correct
21 Correct 304 ms 63868 KB Output is correct
22 Correct 322 ms 63864 KB Output is correct
23 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 63420 KB Output is correct
2 Correct 359 ms 63480 KB Output is correct
3 Correct 358 ms 63480 KB Output is correct
4 Correct 362 ms 63480 KB Output is correct
5 Correct 361 ms 63480 KB Output is correct
6 Correct 282 ms 63608 KB Output is correct
7 Correct 278 ms 63608 KB Output is correct
8 Correct 311 ms 63608 KB Output is correct
9 Correct 304 ms 62712 KB Output is correct
10 Correct 306 ms 63864 KB Output is correct
11 Correct 322 ms 63864 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 360 ms 63352 KB Output is correct
13 Correct 360 ms 63480 KB Output is correct
14 Correct 363 ms 63536 KB Output is correct
15 Correct 364 ms 63608 KB Output is correct
16 Correct 364 ms 63352 KB Output is correct
17 Correct 283 ms 63612 KB Output is correct
18 Correct 283 ms 63608 KB Output is correct
19 Correct 306 ms 63736 KB Output is correct
20 Correct 301 ms 61816 KB Output is correct
21 Correct 304 ms 63868 KB Output is correct
22 Correct 322 ms 63864 KB Output is correct
23 Runtime error 6 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -