Submission #17473708


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SPEED ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define RFOR(i, b, a) for (ll i = b; i >= a; --i)
#define ALL(x) x.begin(), x.end()
#define DEBUG(args...) { string _s = #args; replace(ALL(_s), ' ', '\0');\
replace(ALL(_s), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); _debug(_it, args);}
#define endl "\n"
#define F first
#define S second
#define pb(x) push_back(x)a
#define mp(x, y) make_pair(x, y)

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void _debug(istream_iterator<string>) {}
template<typename T, typename... Args>
void _debug(istream_iterator<string> it, T first, Args... args) {
    cerr << ">> " << *it << " : " << first << endl; _debug(++it, args...);
}
template <typename T1, typename T2>
inline ostream& operator << (ostream& out, const pair<T1, T2>& p) {
    return out << "(" << p.F << ", " << p.S << ")";
}
template<typename T>
inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty()) return out << "[]";
    else { out << '['; for (auto& e : v) { out << e << ", "; } return out << "\b\b]"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const set<T>& s) {
    if (s.empty()) return out << "{}";
    else { out << '{'; for (auto& e : s) { out << e << ", "; } return out << "\b\b}"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const unordered_set<T>& s) {
    return out << set<T>(ALL(s));
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const map<T1, T2>& m) {
    if (m.empty()) return out << "{}";
    out << '{'; for (auto& p : m) { out << p << ", "; } return out << "\b\b}";
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const unordered_map<T1, T2>& m) {
    return out << map<T1, T2>(ALL(m));
}
template<typename T>
inline ostream& operator << (ostream& out, const ordered_set<T>& s) {
    return out << set<T>(ALL(s));
}

typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef unordered_map<ll, ll> STll;
/************************************** MAIN PROGRAM ********************************************/
int n;
const ll INF = 1e18;
ll dp[18][1 << 18];
bool visited[18][1 << 18];
const int MAX = 18;
int x[MAX], y[MAX], z[MAX];


ll dist(int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0, z[j] - z[i]);
}

ll ans(int s, int mask) {
    if (dp[s][mask] != -1) return dp[s][mask];

    if (mask == 0) {
        return dist(s, 0);
    }

    ll res = INF;
    for (int v = 0; v < n; ++v) {
        if (mask >> v & 1) {
            res = min(res, dist(s, v) + ans(v, mask ^ (1 << v)));
        }
    }
  //  DEBUG(s, mask, res, '\n')

    return dp[s][mask] = res;
}

int main()
{
   // freopen("input.txt", "r", stdin);
    SPEED

    memset(dp, -1, sizeof dp);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }
  //  DEBUG(dist(0, 1))
    cout << ans(0, (1 << n) - 2);
}
/************************************** END OF PROGRAM ******************************************/
/** Stuff you should look for:
 * int overflow, array bounds, over-counting
 * special cases (n=1?), set/unordered_set TLE, multi-set/set error
 * do something instead of nothing and stay organized
 */

Submission Info

Submission Time
Task E - Traveling Salesman among Aerial Cities
User manishjoshi394
Language C++ (GCC 9.2.1)
Score 500
Code Size 3717 Byte
Status AC
Exec Time 122 ms
Memory 40512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 122 ms 40500 KB
random_02.txt AC 30 ms 40396 KB
random_03.txt AC 112 ms 40476 KB
random_04.txt AC 112 ms 40384 KB
random_05.txt AC 120 ms 40368 KB
random_06.txt AC 33 ms 40396 KB
random_07.txt AC 106 ms 40344 KB
random_08.txt AC 40 ms 40496 KB
random_09.txt AC 111 ms 40396 KB
random_10.txt AC 28 ms 40420 KB
random_11.txt AC 110 ms 40372 KB
random_12.txt AC 32 ms 40332 KB
random_13.txt AC 119 ms 40420 KB
random_14.txt AC 29 ms 40324 KB
random_15.txt AC 117 ms 40504 KB
random_16.txt AC 34 ms 40472 KB
random_17.txt AC 112 ms 40376 KB
random_18.txt AC 32 ms 40368 KB
random_19.txt AC 103 ms 40324 KB
random_20.txt AC 37 ms 40512 KB
sample_01.txt AC 31 ms 40368 KB
sample_02.txt AC 31 ms 40384 KB
sample_03.txt AC 106 ms 40372 KB