Submission #104087

#	Time	Username	Problem	Language	Result	Execution time	Memory
104087		autumn_eel	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	937 ms	4472 KiB

merchant

#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||d[i][j]==INF)continue;
		a[i][j]=-t*d[i][j];
		rep(k,K){
			if(b[i][k]==-1||s[j][k]==-1)continue;
			a[i][j]=max(a[i][j],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 (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:31: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:35: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: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34