oj.uz

Submission #106011

# Submission time Handle Problem Language Result Execution time Memory
106011 2019-04-16T07:52:59 Z username Travelling Merchant (APIO17_merchant) C++14
33 / 100
 417 ms 2424 KB 
#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid ((l+r)/2)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#include<bits/stdc++.h>
#define int int_fast64_t
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> VI;
#define REP(i,j,k) for(register int i=(j);i<(k);++i)
#define RREP(i,j,k) for(register int i=(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define MST(a,v) memset(a,(v),sizeof a)
#define pb push_back
#define F first
#define S second
#define endl '\n'
//																#define __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(setw(16)<<a[__i]<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
#define double long double
const int maxn=109,maxm=99e2+9,maxk=1e3+9,inf=1ll<<50;
const double eps=1e-7;
int n,m,k,b[maxn][maxk],s[maxn][maxk],t[maxn][maxn],c[maxn][maxn];
double d[maxn][maxn];

bool check(double x){
	REP(i,0,n)REP(j,0,n)d[i][j]=x*t[i][j]-(double)c[i][j];
	REP(i,0,n)REP(j,0,n)REP(p,0,n)MIN(d[i][j],d[i][p]+d[p][j]);
	REP(i,0,n)if(d[i][i]<0)return 1;
	return 0;
}

main(){
	IOS;
	cin>>n>>m>>k;
	REP(i,0,n)REP(j,0,k){
		cin>>b[i][j]>>s[i][j];
		if(b[i][j]<0)b[i][j]=inf;
		if(s[i][j]<0)s[i][j]=-inf;
	}
	REP(i,0,n)REP(j,0,n)t[i][j]=inf,c[i][j]=0;
	REP(i,0,n)t[i][i]=0;
	REP(i,0,m){
		int v,w,tt;cin>>v>>w>>tt,--v,--w;
		t[v][w]=tt;
	}
	REP(i,0,n)REP(j,0,n)REP(p,0,n)MIN(t[i][j],t[i][p]+t[p][j]);
	REP(i,0,n)REP(j,0,n)REP(p,0,k)MAX(c[i][j],s[j][p]-b[i][p]);
	double l=0,r=1e11L+9;
	while(l+eps<r){
		if(check(mid))l=mid;
		else r=mid;
	}
	if(l-floor(l)<=eps)cout<<(int)floor(l)<<endl;
	else if(ceil(l)-l<=eps)cout<<(int)ceil(l)<<endl;
	else cout<<(int)floor(l)<<endl;
}

Compilation message

merchant.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 2424 KB Output is correct
2 Incorrect 373 ms 1536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 1696 KB Output is correct
2 Correct 384 ms 2320 KB Output is correct
3 Correct 389 ms 1592 KB Output is correct
4 Correct 378 ms 1700 KB Output is correct
5 Correct 352 ms 1688 KB Output is correct
6 Correct 417 ms 1588 KB Output is correct
7 Correct 44 ms 956 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 49 ms 984 KB Output is correct
10 Correct 46 ms 964 KB Output is correct
11 Correct 45 ms 1024 KB Output is correct
12 Correct 45 ms 956 KB Output is correct
13 Correct 43 ms 960 KB Output is correct

Subtask #4
0 / 34.0

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