Submission #246875

#	Time	Username	Problem	Language	Result	Execution time	Memory
246875		errorgorn	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	150 ms	4276 KiB

merchant

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,k;
ll buy[105][1005];
ll sell[105][1005];

ll dist[105][105];
ll val[105][105];

ll APSP[105][105];

bool can(ll i){
	rep(x,0,n) rep(y,0,n){
		APSP[x][y]=val[x][y]-dist[x][y]*i;
	}
	
	rep(k,0,n){
		rep(i,0,n){
			rep(j,0,n){
				APSP[i][j]=max(APSP[i][j],APSP[i][k]+APSP[k][j]);
			}
		}
	}
	
	rep(x,0,n) if (APSP[x][x]>=0) return true;
	return false;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	
	rep(x,0,n) rep(y,0,k){
		cin>>buy[x][y]>>sell[x][y];
		
		if (buy[x][y]==-1) buy[x][y]=1e18;
		if (sell[x][y]==-1) sell[x][y]=-1e18;
	}
	
	rep(x,0,n) rep(y,0,n) dist[x][y]=1e9;
	
	int a,b,c;
	rep(x,0,m){
		cin>>a>>b>>c;
		a--,b--;
		
		dist[a][b]=c;
	}
	
	rep(k,0,n){
		rep(i,0,n){
			rep(j,0,n){
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	
	rep(x,0,n) rep(y,0,n){
		rep(z,0,k) val[x][y]=max(val[x][y],sell[y][z]-buy[x][z]);
	}
	
	
	ll lo=0,hi=1e9+100,mi;
	
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (can(mi)) lo=mi;
		else hi=mi;
	}
	
	cout<<lo<<endl;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:100:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mi=hi+lo>>1;
      ~~^~~

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