oj.uz

Submission #106001

# Submission time Handle Problem Language Result Execution time Memory
106001 2019-04-16T07:04:44 Z username Travelling Merchant (APIO17_merchant) C++14
33 / 100
 414 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,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 414 ms 2424 KB Output is correct
2 Incorrect 400 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 50 ms 1020 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 392 ms 1688 KB Output is correct
2 Correct 380 ms 2424 KB Output is correct
3 Correct 382 ms 1536 KB Output is correct
4 Correct 381 ms 1784 KB Output is correct
5 Correct 387 ms 1664 KB Output is correct
6 Correct 382 ms 1656 KB Output is correct
7 Correct 46 ms 896 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 47 ms 896 KB Output is correct
10 Correct 49 ms 896 KB Output is correct
11 Correct 47 ms 1024 KB Output is correct
12 Correct 44 ms 896 KB Output is correct
13 Correct 43 ms 896 KB Output is correct

Subtask #4
0 / 34.0

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