Submission #945489

#	Time	Username	Problem	Language	Result	Execution time	Memory
945489		Wael	Travelling Merchant (APIO17_merchant)	C++17	Compilation error	0 ms	0 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define log(x) (63^__builtin_clzll(x))
#define endl '\n'
#define all(x) (x).begin() , (x).end()
const int mod = 1e9 + 7, lg = 22 , N = 1e6 + 1;
#define int long long

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> b(n, vector<int>(k)), s(n, vector<int>(k));
    for(int i = 0; i < n; ++i) 
        for(int item = 0; item < k; ++item)
            cin >> b[i][item] >> s[i][item];

    vector<vector<int>> dis(n, vector<int>(n, 1e9)), maxGain(n, vector<int>(n, 0));

    for(int i = 0; i < m; ++i) {
        int u, v, len;
        cin >> u >> v >> len;
        --u, --v;
        dis[u][v] = min(dis[u][v], len);
    }

    for(int mid = 0; mid < n; ++mid) 
        for(int start = 0; start < n; ++start)
            for(int end = 0; end < n; ++end)
                dis[start][end] = min(dis[start][end], dis[start][mid] + dis[mid][end]);
    
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(dis[i][j] == 1e9) continue;
            for(int item = 0; item < k; ++item) 
                if(s[j][item] != -1 && b[i][item] != -1)
                   maxGain[i][j] = max(maxGain[i][j], s[j][item] - b[i][item]);
        }
    }
    
    int l = 0, r = 1e9;
    while(l <= r) {
        int mid = (l + r) / 2;
        
        vector<vector<long long>> dp(n, vector<long long>(n, -1e18));
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                if(dis[i][j] == 1e9) continue;
                dp[i][j] = max(dp[i][j], (long long)maxGain[i][j] - (long long)dis[i][j] * mid);
            }
        }

        for(int mid = 0; mid < n; ++mid) 
            for(int start = 0; start < n; ++start)
                for(int end = 0; end < n; ++end)
                    dp[start][end] = max(dp[start][end], dp[start][mid] + dp[mid][end]);

        int ok = 0;
        for(int i = 0; i < n; ++i) {
            if(maxGain[i][i] / dis[i][i] >= mid) ok = 1;
            for(int j = 0; j < n; ++j) {
                if(dis[i][j] == 1e9) continue;
                long long cost = -(long long)dis[i][j] * mid;
                if(dp[j][i] + cost >= 0) ok = 1;
            }
        }

        if(ok) l = mid + 1;
        else r = mid - 1;
    }

    cout << max(0, l - 1) << endl;
    return;
}

main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
   
    int t;
    //cin >> t; 
    t = 1;
    while(t--) solve();

    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'void solve()':
merchant.cpp:71:25: error: no matching function for call to 'max(int, long long int)'
   71 |     cout << max(0, l - 1) << endl;
      |                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from merchant.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
merchant.cpp:71:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   71 |     cout << max(0, l - 1) << endl;
      |                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from merchant.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
merchant.cpp:71:25: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   71 |     cout << max(0, l - 1) << endl;
      |                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from merchant.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
merchant.cpp:71:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   71 |     cout << max(0, l - 1) << endl;
      |                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from merchant.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
merchant.cpp:71:25: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   71 |     cout << max(0, l - 1) << endl;
      |                         ^
merchant.cpp: At global scope:
merchant.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      | ^~~~