Submission #1147458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147458		elitewantsyou	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	55 ms	1352 KiB

merchant

//Hello World;
#define kumi_kumi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("Ofast")
inline void debugMode() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif // ONLINE_JUDGE
}

const int N = 105, K = 1005;
int n, m, k;
int b[N][K], c[N][K], v[N][N];
long long t[N][N], d[N][N];

bool can(int md) {
    
    for(int i = 0; i < n; i++) {
         for(int j = 0; j < n; j++) {
             if (t[i][j] > 1e17) {
                 d[i][j] = -1e18;
             } else {
                 d[i][j] = v[i][j] - t[i][j] * md; 
             }
         }
         d[i][i] = -1e18;
       }
     
       for(int x = 0; x < n; x++) {
         for(int i = 0; i < n; i++) {
           for(int j = 0; j < n; j++) 
             d[i][j] = max(d[i][j], d[i][x] + d[x][j]);
         }
       }
       for (int i = 0; i < n; i++) {
           if (d[i][i] >= 0) return true;
       }
    
    return false;
}

int main () {
    kumi_kumi;
    //debugMode();
     cin >> n >> m >> k;
     for(int i = 0; i < n; i++) {
       for(int j = 0; j < k; j++) 
         cin >> b[i][j] >> c[i][j];
     }
     for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) 
         t[i][j] = 1e18;
       t[i][i] = 0;
     }
     for(int i = 0; i < m; i++) {
       int v1, w1, t1;
       cin >> v1 >> w1 >> t1;
       t[v1 - 1][w1 - 1] = t1;
     }
     for(int x = 0; x < n; x++) {
       for(int i = 0; i < n; i++) {
         for(int j = 0; j < n; j++) 
           t[i][j] = min(t[i][j], t[i][x] + t[x][j]);
         for(int j = 0; j < k; j++) {
             if (c[i][j] != -1 && b[x][j] != -1) {
                 v[x][i] = max(v[x][i], c[i][j] - b[x][j]);
             }
         }
       }
     }
     
     int l = 0, r = 1e9;
     while(l < r) {
       int md = (l + r) / 2;
       if(can(md + 1)) 
         l = md + 1;
       else
         r = md;
     }
     cout << l;
}

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