oj.uz

Submission #101991

# Submission time Handle Problem Language Result Execution time Memory
101991 2019-03-21T09:23:33 Z bakpark Travelling Merchant (APIO17_merchant) C++14
33 / 100
 147 ms 2040 KB 
#include <cstdio>
#include <algorithm>
#include <limits.h>
using namespace std;
#define INF ((LLONG_MAX)>>10)
#define ll long long

int N,M,K;
ll B[101][1001];
ll S[101][1001];
ll T[101][101];
ll tval[101][101];
bool f(ll m){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			tval[i][j] = -INF;
			if(T[i][j] == 0 ) continue;
			for(int k = 1;k<=K;k++){
				bool TF = S[j][k]==-1||B[i][k]==-1;
				ll l=0,r=0;
				if(!TF&&S[j][k]>B[i][k]){
					l = S[j][k];
					r = B[i][k];
				}
				tval[i][j] = max(tval[i][j],l-r-T[i][j]*m);
			}
		}
	}
	for(int k=1;k<=N;k++){
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				tval[i][j] = max(tval[i][j],tval[i][k]+tval[k][j]);
			}
		}
	}
	for(int i=1;i<=N;i++){
		if(tval[i][i]>=0) return true;
	}
	return false;
}




int main(){
	scanf("%d %d %d",&N,&M,&K);
	for(int i=1;i<=N;i++){
		for(int j=0;j<K+K;j++){
			ll tmp;scanf("%lld",&tmp);
			if(j&1)	S[i][j/2+1] = tmp;
			else B[i][j/2+1] = tmp;
		}
	}
	for(int i=0;i<M;i++){
		int a,b;
		ll c;
		scanf("%d %d %lld",&a,&b,&c);
		T[a][b] = c;
	}
	ll l = 0,r = 1000000000,answ=0;
	while(l<=r){
		ll m = (l+r)>>1;
		if(f(m)){
			l = m+1;
			answ = m;
		}
		else r = m-1;
	}
	printf("%lld",answ);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
merchant.cpp:49:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    ll tmp;scanf("%lld",&tmp);
           ~~~~~^~~~~~~~~~~~~
merchant.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2040 KB Output is correct
2 Correct 42 ms 1336 KB Output is correct
3 Correct 50 ms 1280 KB Output is correct
4 Incorrect 8 ms 768 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 768 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 44 ms 1460 KB Output is correct
2 Correct 147 ms 2040 KB Output is correct
3 Correct 43 ms 1280 KB Output is correct
4 Correct 45 ms 1528 KB Output is correct
5 Correct 56 ms 1492 KB Output is correct
6 Correct 46 ms 1280 KB Output is correct
7 Correct 13 ms 768 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 10 ms 888 KB Output is correct
10 Correct 10 ms 896 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 8 ms 768 KB Output is correct
13 Correct 7 ms 768 KB Output is correct

Subtask #4
0 / 34.0

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