oj.uz

Submission #61424

# Submission time Handle Problem Language Result Execution time Memory
61424 2018-07-25T23:51:32 Z Benq Soccer (JOI17_soccer) C++11
100 / 100
 989 ms 28272 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
int H,W,N;
ll A,B,C;
ll dp[501][501][6], dist[501][501]; 
pi st, en, p[MX];
// position
// 0,1,2,3: N,S,E,W 
// 4: no kicker
// 5: yes kicker

bool valid(pi a) {
    return 0 <= a.f && a.f <= H && 0 <= a.s && a.s <= W;
}

typedef array<ll,4> T;
priority_queue<T,vector<T>,greater<T>> P; 

void tri(int p0, int p1, int z, ll res) {
    if (!valid({p0,p1})) return;
    if (dp[p0][p1][z] <= res) return;
    P.push({dp[p0][p1][z] = res,p0,p1,z});
} 

void shPath() {
    P.push({dp[st.f][st.s][4] = 0,st.f,st.s,4});
    while (sz(P)) {
        auto a = P.top(); P.pop();
        if (a[0] > dp[a[1]][a[2]][a[3]]) continue;
        // cout << a[0] << " " << a[1] << " " << a[2] << " " << a[3] << "\n";
        if (a[3] < 4) {
            tri(a[1]+xd[a[3]],a[2]+yd[a[3]],a[3],a[0]+A); // move in some dir
            tri(a[1],a[2],4,dp[a[1]][a[2]][a[3]]); // stop moving 
        } else if (a[3] == 4) {
            tri(a[1],a[2],5,a[0]+C*dist[a[1]][a[2]]); // take the ball
        } else {
            F0R(i,4) {
                tri(a[1],a[2],i,a[0]+B); // kick it in some dir
                tri(a[1]+xd[i],a[2]+yd[i],5,a[0]+C); // move in some dir
            }
            tri(a[1],a[2],4,a[0]);
        }
    }
    
    cout << dp[en.f][en.s][4];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> H >> W >> A >> B >> C >> N;
    F0R(i,N) cin >> p[i].f >> p[i].s;
    st = p[0], en = p[N-1];
    F0R(i,H+1) F0R(j,W+1) {
        dist[i][j] = INF;
        F0R(k,6) dp[i][j][k] = INF;
    }
    queue<pi> q;
    F0R(i,N) {
        dist[p[i].f][p[i].s] = 0;
        q.push(p[i]);
    }
    while (sz(q)) {
        pi a = q.front(); q.pop();
        F0R(i,4) {
            pi A = {a.f+xd[i],a.s+yd[i]};
            if (!valid(A) || dist[A.f][A.s] != INF) continue;
            dist[A.f][A.s] = dist[a.f][a.s]+1;
            q.push(A);
        }
    }
    
    /*F0R(i,H+1) {
        F0R(j,W+1) cout << dist[i][j];
        cout << "\n";
    }*/
    shPath();
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 7788 KB Output is correct
2 Correct 2 ms 7788 KB Output is correct
3 Correct 738 ms 22520 KB Output is correct
4 Correct 709 ms 22700 KB Output is correct
5 Correct 141 ms 22700 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 22732 KB Output is correct
2 Correct 770 ms 22816 KB Output is correct
3 Correct 553 ms 22816 KB Output is correct
4 Correct 508 ms 22820 KB Output is correct
5 Correct 514 ms 22820 KB Output is correct
6 Correct 566 ms 22972 KB Output is correct
7 Correct 650 ms 23116 KB Output is correct
8 Correct 615 ms 23116 KB Output is correct
9 Correct 769 ms 23116 KB Output is correct
10 Correct 107 ms 23116 KB Output is correct
11 Correct 741 ms 23116 KB Output is correct
12 Correct 749 ms 23116 KB Output is correct
13 Correct 373 ms 23116 KB Output is correct
14 Correct 786 ms 23116 KB Output is correct
15 Correct 623 ms 23116 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 7788 KB Output is correct
2 Correct 2 ms 7788 KB Output is correct
3 Correct 738 ms 22520 KB Output is correct
4 Correct 709 ms 22700 KB Output is correct
5 Correct 141 ms 22700 KB Output is correct
6 Correct 804 ms 22732 KB Output is correct
7 Correct 770 ms 22816 KB Output is correct
8 Correct 553 ms 22816 KB Output is correct
9 Correct 508 ms 22820 KB Output is correct
10 Correct 514 ms 22820 KB Output is correct
11 Correct 566 ms 22972 KB Output is correct
12 Correct 650 ms 23116 KB Output is correct
13 Correct 615 ms 23116 KB Output is correct
14 Correct 769 ms 23116 KB Output is correct
15 Correct 107 ms 23116 KB Output is correct
16 Correct 741 ms 23116 KB Output is correct
17 Correct 749 ms 23116 KB Output is correct
18 Correct 373 ms 23116 KB Output is correct
19 Correct 786 ms 23116 KB Output is correct
20 Correct 623 ms 23116 KB Output is correct
21 Correct 148 ms 23116 KB Output is correct
22 Correct 989 ms 23200 KB Output is correct
23 Correct 842 ms 23200 KB Output is correct
24 Correct 939 ms 23200 KB Output is correct
25 Correct 698 ms 23436 KB Output is correct
26 Correct 748 ms 23452 KB Output is correct
27 Correct 428 ms 23452 KB Output is correct
28 Correct 507 ms 23452 KB Output is correct
29 Correct 601 ms 23452 KB Output is correct
30 Correct 355 ms 23452 KB Output is correct
31 Correct 658 ms 25972 KB Output is correct
32 Correct 986 ms 28272 KB Output is correct
33 Correct 508 ms 28272 KB Output is correct
34 Correct 973 ms 28272 KB Output is correct
35 Correct 382 ms 28272 KB Output is correct