oj.uz

Submission #104084

# Submission time Handle Problem Language Result Execution time Memory
104084 2019-04-04T00:09:29 Z autumn_eel Travelling Merchant (APIO17_merchant) C++14
0 / 100
 779 ms 4200 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){
		int 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

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1152 KB Output is correct
2 Incorrect 9 ms 1152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 1868 KB Output is correct
2 Correct 779 ms 4200 KB Output is correct
3 Correct 102 ms 1784 KB Output is correct
4 Correct 126 ms 1920 KB Output is correct
5 Correct 131 ms 2040 KB Output is correct
6 Correct 82 ms 1756 KB Output is correct
7 Correct 21 ms 1152 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 21 ms 1152 KB Output is correct
10 Correct 21 ms 1280 KB Output is correct
11 Incorrect 22 ms 1152 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1152 KB Output is correct
2 Incorrect 9 ms 1152 KB Output isn't correct
3 Halted 0 ms 0 KB -