Submission #329409

#	Time	Username	Problem	Language	Result	Execution time	Memory
329409		lohacho	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	108 ms	5100 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const LL MOD = (LL)1e9 + 7;
LL N, M, k;
LL val[104][1004][3];
LL prof[104][104];
vector<vector<LL>> dis, gr;

void floid(auto&gra){
    for(LL c = 1; c <= N; ++c){
        for(LL a = 1; a <= N; ++a){
            for(LL b = 1; b <= N; ++b){
                gra[a][b] = min(gra[a][b], gra[a][c] + gra[c][b]);
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> k;
    for(LL i = 1; i <= N; ++i){
        for(LL j = 1; j <= k; ++j){
            cin >> val[i][j][1] >> val[i][j][2];
        }
    }
    for(LL i = 1; i <= N; ++i){
        for(LL j = 1; j <= N; ++j){
            for(LL x = 1; x <= k; ++x){
                if(val[i][x][1] != -1 && val[j][x][2] != -1){
                    prof[i][j] = max(prof[i][j], val[j][x][2] - val[i][x][1]);
                }
            }
        }
    }
    dis.resize(N + 4);
    for(LL i = 1; i <= N; ++i){
        dis[i].resize(N + 4);
        for(LL j = 1; j <= N; ++j){
            dis[i][j] = MOD;
        }
    }
    for(LL i = 1, a, b, c; i <= M; ++i){
        cin >> a >> b >> c;
        dis[a][b] = c;
    }
    floid(dis);
    LL low = 0, high = MOD, mid;
    while(low < high){
        mid = (low + high) >> 1; ++mid;
        gr = dis;
        for(LL i = 1; i <= N; ++i){
            for(LL j = 1; j <= N; ++j){
                gr[i][j] = dis[i][j] * mid - prof[i][j];
            }
        }
        floid(gr);
        LL f = 0;
        for(LL i = 1; i <= N; ++i){
            if(gr[i][i] <= 0){
                f = 1;
                break;
            }
        }
        if(f){
            low = mid;
        }
        else{
            high = mid - 1;
        }
    }
    cout << low;
    return 0;
}

Compilation message (stderr)

merchant.cpp:12:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   12 | void floid(auto&gra){
      |            ^~~~

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