Submission #110602

#	Time	Username	Problem	Language	Result	Execution time	Memory
110602		tictaccat	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	195 ms	4344 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 2e9;
const int MAX_N = 100;
const int MAX_K = 1000;

int N,M,K;
vector<vector<int>> adj(MAX_N,vector<int>(MAX_N,INF));
vector<vector<int>> d(MAX_N,vector<int>(MAX_N,INF)), v(MAX_N,vector<int>(MAX_N,0));
vector<vector<int>> B(MAX_N, vector<int>(MAX_K)), S(MAX_N, vector<int>(MAX_K));

bool check(int t) {
    vector<vector<int>> dist(N,vector<int>(N));
    for (int k = -1; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (k == -1) dist[i][j] = t*d[i][j] - v[i][j];
                else dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i = 0; i < N; i++) if (dist[i][i] <= 0) return true;
    return false;
}

main() {

    cin >> N >> M >> K;

    for (int i = 0; i < N; i++) {
        for (int z = 0; z < K; z++) {
            cin >> B[i][z] >> S[i][z];
            if (B[i][z] == -1) B[i][z] = INF;
            if (S[i][z] == -1) S[i][z] = 0;
        }
    }    

    for (int i = 0; i < M; i++) {
        int V,W,P; cin >> V >> W >> P;
        d[V-1][W-1] = P;
    }

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int z = 0; z < K; z++) {
                v[i][j] = max(v[i][j],S[j][z] - B[i][z]);
            }
        }
    }

    int t = 0; int high = 2e9;

    for (int b = high/2; b > 0; b /= 2) {
        while (t + b < high && check(t + b)) t += b;
    }

    cout << t << "\n";


    return 0;
}

Compilation message (stderr)

merchant.cpp:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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