Submission #263439

#	Time	Username	Problem	Language	Result	Execution time	Memory
263439		shayan_p	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	115 ms	1448 KiB

merchant

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 110, maxk = 1010, mod = 1e9 + 7, big = 1e9 + 10;
const ll inf = 4e18;

pii p[maxn][maxk];
ll d[maxn][maxn], dd[maxn][maxn], g[maxn][maxn];
int n;

bool floyd(ll a[][maxn]){    
    for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
	    for(int k = 0; k < n; k++)
		a[j][k] = min(a[j][k], a[j][i] + a[i][k]);
    for(int i = 0; i < n; i++)
	if(a[i][i] <= 0)
	    return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int m, k;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){
	for(int j = 0; j < k; j++){
	    cin >> p[i][j].F >> p[i][j].S;
	}
    }
    for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++)
	    d[i][j] = inf;
	d[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
	int a, b, c;
	cin >> a >> b >> c;
	--a, --b;
	d[a][b] = min(d[a][b], ll(c));
    }
    floyd(d);
    for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++){
	    if(d[i][j] != inf){
		for(int w = 0; w < k; w++){
		    if(p[i][w].F < p[j][w].S && p[i][w].F != -1 && p[j][w].S != -1)
			dd[i][j] = max(dd[i][j], ll(p[j][w].S - p[i][w].F));
		}
	    }
	}
    }
    
    for(int i = 0; i < n; i++)
	for(int j = 0; j < n; j++)
	    assert(d[i][j] == inf || d[i][j] <= big), assert(dd[i][j] <= big);
    
    int l = 0, r = big;
    while(r-l > 1){
	int mid = (l+r) >> 1;
	for(int i = 0; i < n; i++)
	    for(int j = 0; j < n; j++)
		g[i][j] = (d[i][j] == inf || i == j) ? (inf) : (1ll * mid * d[i][j] - dd[i][j]);
	if(floyd(g))
	    l = mid;
	else
	    r = mid;
    }
    assert(r != big);
    return cout << l << endl, 0;
}

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