Submission #750328

#	Time	Username	Problem	Language	Result	Execution time	Memory
750328		boris_7	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	170 ms	2432 KiB

merchant

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<ll>>b(n,vector<ll>(k)),s(n,vector<ll>(k));
    for(int i = 0;i<n;i++){
        for(int j = 0;j<k;j++){
            cin>>b[i][j]>>s[i][j];
        }
    }
    vector<vector<pair<ll,ll>>>gp(n);
    vector<vector<ll>>d(n,vector<ll>(n,1e18));
    for(int i = 0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        gp[--u].push_back({--v,w});
        d[u][v]=w;
    }
    for(int p = 0;p<n;p++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                d[i][j] = min(d[i][j],d[i][p]+d[p][j]);
            }
        }
    }
    vector<vector<ll>>max_delta(n,vector<ll>(n));
    for(int p = 0;p<k;p++){
        for(int i = 0;i<n;i++){
            for(int j= 0;j<n;j++){
                if(b[i][p]!=-1 && s[j][p]!=-1){
                    max_delta[i][j] = max(max_delta[i][j], s[j][p] - b[i][p]);
                }
            }
        }
    }
    ll l = 0,r = 1e15;
    while(l+1<r){
        vector<vector<long long>> d1(n, vector<long long>(n, -1e18));
        long long m = (l + r) / 2;
		for (int i=0;i<n;++i) {
			for (int j=0;j<n;++j) {
				long long p=1e18/m;
				d1[i][j]=max_delta[i][j]-m*min(p,d[i][j]);
			}
		}
		for (int p=0;p<n;++p) {
			for (int i=0;i<n;++i) {
				for (int j=0;j<n;++j) {
					d1[i][j] = max(d1[i][j], d1[i][p] + d1[p][j]);
				}
			}
		}
		bool f = 0;
		for (int i = 0; i < n; ++i) if (d1[i][i] >= 0) f = 1;
		d1 = vector<vector<long long>>(n, vector<long long>(n, -1e18));
		if (f) l = m;
		else r = m;
    }
    cout<<l<<endl;
}

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