Submission #156999

#	Time	Username	Problem	Language	Result	Execution time	Memory
156999		Mercenary	Travelling Merchant (APIO17_merchant)	C++14	21 / 100	45 ms	760 KiB

merchant

#include<bits/stdc++.h>
#define taskname "A"
#define pb push_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
#define next aoisfdhjaoif
const int maxn = 1e2 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e11 + 1;

int n , m , k;

int s[maxn][maxn] , b[maxn][maxn];

int profit[maxn][maxn];
ll dis[maxn][maxn];
ll dis1[maxn][maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= k ; ++j){
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            for(int t = 1 ; t <= k ; ++t){
                if(s[j][t] != -1 && b[i][t] != -1)
                   profit[i][j] = max(profit[i][j] , s[j][t] - b[i][t]);
            }
        }
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            dis[i][j] = inf;
        }
    }
    for(int i = 1 ; i <= m ; ++i){
        int u , v , w;cin >> u >> v >> w;
        dis[u][v] = min(dis[u][v] , (ll)w);
    }
    for(int t = 1 ; t <= n ; ++t){
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= n ; ++j){
                dis[i][j] = min(dis[i][j] , dis[i][t] + dis[t][j]);
            }
        }
    }
    int l = 1;
    int h = 1e9;
//    for(int i = 1 ; i <= n ; ++i){
//        for(int j = 1 ; j <= n ; ++j)cout << dis[i][j] << " \n"[j == n];
//    }
//    for(int i = 1 ; i <= n ; ++i){
//        for(int j = 1 ; j <= n ; ++j)cout << profit[i][j] << " \n"[j == n];
//    }
    while(l <= h){
        int mid = l + h >> 1;
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= n ; ++j){
                if(1e15 / mid < dis[i][j])dis1[i][j] = 1e13 + 1;
                else dis1[i][j] = min(inf,dis[i][j] * mid - profit[i][j]);
            }
        }
        for(int t = 1 ; t <= n ; ++t){
            for(int i = 1 ; i <= n ; ++i){
                for(int j = 1 ; j <= n ; ++j){
                    dis1[i][j] = min(dis1[i][j] , dis1[i][t] + dis1[t][j]);
                }
            }
        }
        bool ok = 0;
        for(int i = 1 ; i <= n ; ++i)ok |= dis1[i][i] <= 0;
        if(ok == 0)h = mid - 1;
        else l = mid + 1;
    }
    cout << h;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + h >> 1;
                   ~~^~~
merchant.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP","r",stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".OUT","w",stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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