Submission #630189

#	Time	Username	Problem	Language	Result	Execution time	Memory
630189		Shreyan_Paliwal	Travelling Merchant (APIO17_merchant)	C++17	21 / 100	89 ms	2096 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

using T = long long;

const int maxn = 100;
const int maxk = 1000;
const int maxm = 9900;
const T INF = 0x3fff'ffff'ffff;

int n, m, k; // n markets, m pathways, k items
T items[maxn][maxk][2]; // n markets, k items per market, buy/sell = price of buy/sell
T grid[maxn][maxn]; // adj matrix

T streaks[maxn][maxn];
T temp_streaks[maxn][maxn];

int main() {
    cin.tie(nullptr)->ios::sync_with_stdio(false);

    // freopen("main.in", "r", stdin);

    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < k; j++) 
            for (int l = 0; l < 2; l++)
                cin >> items[i][j][l];

    fill(&grid[0][0], &grid[0][0] + sizeof(grid) / sizeof(grid[0][0]), INF);

    for (int i = 0; i < m; i++) {
        int a, b; T c; cin >> a >> b >> c; a--, b--;
        grid[a][b] = min(grid[a][b], c);
    }

    // floyd warshall on grid
    for (int l = 0; l < n; l++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                grid[i][j] = min(grid[i][j], grid[i][l] + grid[l][j]);


    // creating streaks
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int l = 0; l < k; l++)
                if (items[j][l][1] != -1 && items[i][l][0] != -1)
                    streaks[i][j] = max(streaks[i][j], items[j][l][1] - items[i][l][0]);

    // bin search on answer
    T lo = 0, hi = maxk * 1e9 * 10;
    while (lo < hi) {
        T mid = (lo + hi + 1) >> 1;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                temp_streaks[i][j] = (grid[i][j] == INF ? -INF : streaks[i][j] - mid * grid[i][j]);

        // for (int i = 0; i < n; i++)
        //     temp_streaks[i][i] = -INF;
 
        for (int l = 0; l < n; l++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    temp_streaks[i][j] = max(temp_streaks[i][j], temp_streaks[i][l] + temp_streaks[l][j]);   

        bool works = false;
        for (int i = 0; i < n && !works; i++)
            works |= temp_streaks[i][i] >= 0;

        if (works)
            lo = mid;
        else 
            hi = mid - 1;
    }

    // output
    cout << lo << '\n';

    return 0;
}

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