Submission #512192

#	Time	Username	Problem	Language	Result	Execution time	Memory
512192		InternetPerson10	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	69 ms	3140 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<vector<ll>> b, s;
vector<vector<pair<int, int>>> adj;
ll dist[100][100], gain[100][100];

const ll BIG = 1234567890;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    b.resize(n);
    s.resize(n);
    adj.resize(n);
    for(int i = 0; i < n; i++) {
        b[i].resize(k);
        s[i].resize(k);
        for(int j = 0; j < k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
        for(int j = 0; j < n; j++) {
            dist[i][j] = BIG;
            gain[i][j] = 0;
        }
    }
    for(int i = 0; i < m; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        x--; y--;
        adj[x].push_back({y, t});
        dist[x][y] = t;
    }
    // floyd-warshall
    for(int z = 0; z < n; z++) {
        for(int x = 0; x < n; x++) {
            for(int y = 0; y < n; y++) {
                dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
            }
        }
    }
    // gain calculation
    for(int x = 0; x < n; x++) {
        for(int y = 0; y < n; y++) {
            for(int i = 0; i < k; i++) {
                if(b[x][i] == -1 || s[y][i] == -1) continue;
                gain[x][y] = max(gain[x][y], s[y][i] - b[x][i]);
            }
        }
    }
    // Subtask 1
    ll ans = 0;
    for(int i = 1; i < n; i++) {
        ans = max(ans, (gain[0][i] + gain[i][0])/(dist[0][i] + dist[i][0]));
    }
    cout << ans << '\n';
}

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