Submission #61424

#	Time	Username	Problem	Language	Result	Execution time	Memory
61424		Benq	Soccer (JOI17_soccer)	C++11	100 / 100	989 ms	28272 KiB

soccer

#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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65