Submission #261190

#	Time	Username	Problem	Language	Result	Execution time	Memory
261190		evpipis	Travelling Merchant (APIO17_merchant)	C++11	100 / 100	132 ms	1408 KiB

merchant

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

typedef long long ll;

const int len = 105, max_k = 1005, inf = 1e9+10;
const ll long_inf = 1e18+10;

int n, m, k;
int dis[len][len], prof[len][len], buy[len][max_k], sell[len][max_k];
ll path[len][len], state[len];

bool check(int c){
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            path[i][j] = long_inf;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dis[i][j] != inf)
                path[i][j] = c*1LL*dis[i][j] - prof[i][j];

    for (int d = 0; d < n; d++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++){
                // overflows without the -long_inf border
                //if (i == d || d == j)
                  //  continue;
                if (path[i][d] != long_inf && path[d][j] != long_inf)
                    path[i][j] = min(path[i][j], path[i][d]+path[d][j]);
                if (path[i][j] < -long_inf)
                    path[i][j] = -long_inf;
                assert(path[i][j] >= -long_inf);
            }

    // overflows without the -long_inf border
    for (int i = 0; i < n; i++)
        if (path[i][i] <= 0)
            return true;
    return false;
}

int bs(){
    int l = 1, r = 1e9, ans = 0;
    while (l <= r){
        int mid = (l+r)/2;
        if (check(mid))
            ans = mid, l = mid+1;
        else
            r = mid-1;
    }

    return ans;
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            scanf("%d %d", &buy[i][j], &sell[i][j]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = inf;

    for (int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        dis[a-1][b-1] = c;
    }

    // fix dis, prof...
    for (int d = 0; d < n; d++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dis[i][j] = min(dis[i][j], dis[i][d]+dis[d][j]);

    for (int a = 0; a < n; a++)
        for (int b = 0; b < n; b++)
            for (int d = 0; d < k; d++)
                if (buy[a][d] != -1 && sell[b][d] != -1)
                    prof[a][b] = max(prof[a][b], sell[b][d]-buy[a][d]);

    printf("%d\n", bs());
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &buy[i][j], &sell[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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