Submission #252939

#	Time	Username	Problem	Language	Result	Execution time	Memory
252939		Badrangiikh	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	37 ms	4600 KiB

merchant

#include<bits/stdc++.h>
#include <deque> 
#include <cmath>
using namespace std;
 
#define ll long long 
 
/*freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);*/
 
long long n , m , k , i , maxx , minn , x , y , j , z , sz , l ;
map < pair < long long , long long > , long long > mp ;
long long path [ 145 ] [ 145 ] ;
long long price [ 145 ] [ 1045 ] [ 5 ] ;
long long price1 [ 145 ] [ 1045 ] ;

int main() {
    scanf ( "%lld%lld%lld" , & n , & m , & k ) ;
    maxx = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= k ; j ++ ) {
            scanf ( "%lld%lld" , & x , & y ) ;
            price [ i ] [ j ] [ 1 ] = x ;
            price [ i ] [ j ] [ 2 ] = y ;
        }
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= n ; j ++ ) {
            for ( l = 1 ; l <= k ; l ++ ) {
                if ( price [ i ] [ l ] [ 1 ] == -1 || price [ j ] [ l ] [ 2 ] == -1 ) continue ;
                price1 [ i ] [ j ] = max ( price1 [ i ] [ j ] , price [ j ] [ l ] [ 2 ] - price [ i ] [ l ] [ 1 ] ) ;
            }
        }
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= n ; j ++ ) {
            path [ i ] [ j ] = 1234567890 ;
            if ( i == j ) path [ i ] [ j ] = 0 ;
        } 
    }
    for ( i = 1 ; i <= m ; i ++ ) {
        scanf ( "%lld%lld%lld" , & x , & y , & z ) ;
        path [ x ] [ y ] = z ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= n ; j ++ ) {
            for ( l = 1 ; l <= n ; l ++ ) {
                path [ j ] [ l ] = min ( path [ j ] [ l ] , path [ j ] [ i ] + path [ i ] [ l ] ) ;
            }
        }
    }
    maxx = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= n ; j ++ ) {
            if ( i == j ) continue ;
            x = ( price1 [ i ] [ j ] + price1 [ j ] [ i ] ) / ( path [ i ] [ j ] + path [ j ] [ i ] ) ;
            maxx = max ( maxx , x ) ;
        }
    }
    printf ( "%lld" , maxx ) ;
}    

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:18:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%lld%lld%lld" , & n , & m , & k ) ;
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:22:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%lld%lld" , & x , & y ) ;
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:42:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%lld%lld%lld" , & x , & y , & z ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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