oj.uz

Submission #64249

# Submission time Handle Problem Language Result Execution time Memory
64249 2018-08-03T16:45:57 Z khohko Travelling Merchant (APIO17_merchant) C++17
0 / 100
 1000 ms 1508 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+500))
#define MAX ((ll)(1e18+100))
#define MOD ((ll)1e6+7)
#define mi(a,b) a=min((a),(b))


ll n,m,k;
pair<ll,ll> q[200][200];
__int128 f[200][200];
__int128 v[200][200];


int main(){
	#ifdef KHOKHO
			freopen("in.in","r",stdin);
			freopen("out.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	//cout<<n<<" "<<k<<endl;
	for(int i=0; i<n; i++)
		for(int j=0; j<k; j++)
			cin>>q[i][j].fr>>q[i][j].sc;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			f[i][j]=f[j][i]=MAX;
	for(int i=0; i<m; i++){
		ll k,p,c;
		cin>>k>>p>>c;
		k--;
		p--;
		f[k][p]=c;
	}
	//return 0;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			for(int k=0; k<n; k++)
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

	__int128 l=0,r=MAX;
	while(l<r){
		__int128 em=(l+r+1)>>1ll;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				v[i][j]=-em*f[i][j];
				for(int t=0; t<k; t++){
					if(q[i][t].fr>=0&&q[j][t].sc>=0)
						v[i][j]=max(v[i][j],q[j][t].sc-q[i][t].fr-em*f[i][j]);
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				for(int k=0; k<n; k++){
					v[i][j]=max(v[i][j],v[i][k]+v[k][j]);
				}
			}
		}
		bool e=0;
		for(int i=0; i<n; i++){
			if(v[i][i]>=0)
				e=1;
		}
		if(e)
			l=em;
		else r=em-1;
	}
	ll t=l;
	cout<<t;

}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 846 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 1436 KB Output is correct
2 Execution timed out 1076 ms 1508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 1400 KB Output isn't correct
2 Halted 0 ms 0 KB -