Submission #46657

#	Time	Username	Problem	Language	Result	Execution time	Memory
46657		eropsergeev	Soccer (JOI17_soccer)	C++14	30 / 100	14 ms	8636 KiB

soccer

#ifdef LOCKAL
    #define _GLIBCXX_DEBUG
#endif
//#ifndef LOCKAL
    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,mmx,avx")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("unroll-all-loops")
//#endif
#include <bits/stdc++.h>
//#define TIMUS
//#define FILENAME "journey"
#ifndef TIMUS
    #include <ext/rope>
    #include <ext/pb_ds/assoc_container.hpp>
#endif // TIMUS
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int INF = INT_MAX / 2;
const ll LINF = (ll)2e18 + 666, M = 1e9 + 7;
const ld EPS = 1e-7;

#ifndef M_PI
    const ld M_PI = acos(-1);
#endif // M_PI

using namespace std;

#ifndef TIMUS
    using namespace __gnu_cxx;
    using namespace __gnu_pbds;

    template<class K, class T>
    using ordered_map = tree<K, T, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

    template<class T>
    using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

void run();

template<class T1, class T2>
inline bool mini(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}

template<class T1, class T2>
inline bool maxi(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}

int main()
{
    #ifndef LOCKAL
        #ifdef FILENAME
            freopen(FILENAME".in", "r", stdin);
            freopen(FILENAME".out", "w", stdout);
        #endif // FILENAME
    #endif
    #ifndef TIMUS
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    #endif // TIMUS
    srand(time(0));
    auto start = clock();
    run();
    #ifdef LOCKAL
        //cout << endl;
        cout << "\ntime = " << (ld)(clock() - start) / CLOCKS_PER_SEC << "\n";
    #endif
    return 0;
}

#define DEBUG
#if defined DEBUG && defined LOCKAL
    #define debugdo(x) x
#else
    #define debugdo(x)
#endif

#define debug_for(x) debug(#x": "); debugdo(for (auto &_x: x)) debug2(_x); debug("")
#define debug(x) debugdo(cout << x << endl)
#define debug2(x) debugdo(cout << x << " ")

// ---SOLUTION--- //

//#define FAST 1e9
#ifdef FAST
    char buf[(int)FAST];
    size_t p = 0;
    inline void *operator new(size_t n)
    {
        p += n;
        return buf + p - n;
    }
    inline void operator delete(void *){}
#endif

ll d[1000][1000];
int n;

ll dijk()
{
    vector<ll> dst(n, LINF);
    dst[0] = 0;
    vector<bool> use(n);
    for (int i = 0; i < n; i++)
    {
        int p = -1;
        for (int j = 0; j < n; j++)
        {
            if (!use[j] && (p == -1 || dst[p] > dst[j]))
                p = j;
        }
        use[p] = 1;
        for (int j = 0; j < n; j++)
        {
            if (dst[j] > dst[p] + d[p][j])
                dst[j] = dst[p] + d[p][j];
        }
    }
    return dst[n - 1];
}

void run()
{
    int w, h;
    cin >> w >> h;
    ll a, b, c;
    cin >> a >> b >> c;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            d[i][j] = min((abs(x[i] - x[j]) + abs(y[i] - y[j])) * c, min(abs(x[i] - x[j]), abs(y[i] - y[j])) * c + b);
            debug2(d[i][j]);
        }
        debug("");
    }
    cout << dijk();
}
/*

*/

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:86:10: warning: unused variable 'start' [-Wunused-variable]
     auto start = clock();
          ^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65