Submission #1147444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147444		elitewantsyou	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	35 ms	1348 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];

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][w1] = 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++) 
           v[x][i] = max(v[x][i], c[i][j] - b[x][j]);
       }
     }
     int l = 0, r = 1e9;
     while(l + 1 < r) {
       int md = (l + r) >> 1;
       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]);
         }
       }
       bool g = 0;
       for(int i = 0; i < n; i++) 
         g |= (d[i][i] >= 0);
       if(g) 
         l = md;
       else
         r = md;
     }
     cout << l;
}

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