oj.uz

답안 #106008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106008 2019-04-16T07:38:34 Z username 여행하는 상인 (APIO17_merchant) C++14
33 / 100
 558 ms 2384 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

# 결과 실행 시간 메모리 Grader output
1 Correct 453 ms 2384 KB Output is correct
2 Incorrect 347 ms 1536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 1672 KB Output is correct
2 Correct 558 ms 2168 KB Output is correct
3 Correct 408 ms 1572 KB Output is correct
4 Correct 362 ms 1784 KB Output is correct
5 Correct 351 ms 1784 KB Output is correct
6 Correct 357 ms 1656 KB Output is correct
7 Correct 47 ms 896 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 52 ms 896 KB Output is correct
10 Correct 53 ms 992 KB Output is correct
11 Correct 52 ms 896 KB Output is correct
12 Correct 47 ms 896 KB Output is correct
13 Correct 44 ms 896 KB Output is correct

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 936 KB Output isn't correct
2 Halted 0 ms 0 KB -