oj.uz

답안 #104085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104085 2019-04-04T00:13:51 Z autumn_eel 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 828 ms 2424 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;

int n,m,K;
ll d[200][200],a[200][200];
int b[200][2000],s[200][2000];

bool C(ll t){
	rep(i,n)rep(j,n)a[i][j]=-INF;
	rep(i,n)rep(j,n){
		if(i==j)continue;
		rep(k,K){
			if(b[i][k]==-1||s[j][k]==-1)continue;
			a[i][j]=max(a[i][j],max(0,s[j][k]-b[i][k])-t*d[i][j]);
		}
	}
	rep(k,n)rep(i,n)rep(j,n){
		a[i][j]=max(a[i][j],a[i][k]+a[k][j]);
	}
	rep(i,n){
		if(a[i][i]>=0)return true;
	}
	return false;
}
int main(){
	cin>>n>>m>>K;
	rep(i,n)rep(j,K)scanf("%d%d",&b[i][j],&s[i][j]);
	memset(d,0x3f,sizeof(d));
	rep(i,n)d[i][i]=0;
	rep(i,m){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);a--;b--;
		d[a][b]=c;
	}
	rep(k,n)rep(i,n)rep(j,n){
		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	}
	ll l=0,r=INT_MAX;
	while(r-l>1){
		ll t=(l+r)/2;
		if(C(t))l=t;
		else r=t;
	}
	cout<<l<<endl;
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:30:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i,n)rep(j,K)scanf("%d%d",&b[i][j],&s[i][j]);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c;scanf("%d%d%d",&a,&b,&c);a--;b--;
             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 1784 KB Output is correct
2 Correct 828 ms 2340 KB Output is correct
3 Correct 85 ms 1656 KB Output is correct
4 Correct 151 ms 1696 KB Output is correct
5 Correct 134 ms 1700 KB Output is correct
6 Correct 99 ms 1656 KB Output is correct
7 Correct 19 ms 1152 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 18 ms 1152 KB Output is correct
10 Correct 20 ms 1124 KB Output is correct
11 Incorrect 20 ms 1168 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

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