Submission #334075

#	Time	Username	Problem	Language	Result	Execution time	Memory
334075		mohamedsobhi777	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	102 ms	4332 KiB

merchant

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>

using ll = long long;
using ld = long double;

const int N = 1e2 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n, m, k;
vector<pair<ll, ll>> mrs[N];
ll cost[N][N];
ll d[N][N];

ll g[N][N];

bool check(ll mid)
{
        for (int i = 0; i < n; ++i)
        {
                for (int j = 0; j < n; ++j)
                {
                        if (d[i][j] < 1e15)
                                g[i][j] = cost[i][j] - d[i][j] * mid;
                        else
                                g[i][j] = -1e15;
                }
        }
        for (int k = 0; k < n; ++k)
                for (int i = 0; i < n; ++i)
                        for (int j = 0; j < n; ++j)
                                g[i][j] = max(g[i][j], g[i][k] + g[k][j]);
        for (int i = 0; i < n; ++i)
                if (g[i][i] >= 0)
                        return 1;
        return 0;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> m >> k;
        for (int i = 0; i < n; ++i)
        {
                for (int j = 0; j < k; ++j)
                {
                        pii v;
                        cin >> v.f >> v.s;
                        mrs[i].pb(v);
                }
        }
        for (int i = 0; i < n; ++i)
                fill(d[i], d[i] + N, 1e15);

        for (int i = 0; i < m; ++i)
        {
                int u, v, w;
                cin >> u >> v >> w;
                --u;
                --v;
                d[u][v] = min(d[u][v], 1ll * w);
        }

        for (int k = 0; k < n; ++k)
        {
                for (int i = 0; i < n; ++i)
                {
                        for (int j = 0; j < n; ++j)
                        {
                                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                        }
                }
        }
        
        for (int i = 0; i < n; ++i)
        {
                for (int j = 0; j < n; ++j)
                {
                        for (int r = 0; r < k; ++r)
                        {
                                if (~mrs[i][r].f && ~mrs[j][r].s && d[i][j]<1e15)
                                        cost[i][j] = max(cost[i][j], mrs[j][r].s - mrs[i][r].f);
                        }
                }
        }

        ll lo = 0, hi = 1e9;
        ll ans = 0;
        while (lo <= hi)
        {
                ll mid = (lo + hi) >> 1;
                if (check(mid))
                        lo = mid + 1, ans = mid;
                else
                        hi = mid - 1;
        }
        cout << ans;
        return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34