oj.uz

Submission #80300

# Submission time Handle Problem Language Result Execution time Memory
80300 2018-10-19T21:38:01 Z Plurm Travelling Merchant (APIO17_merchant) C++11
0 / 100
 105 ms 1800 KB 
#include <bits/stdc++.h>
using namespace std;
int b[128][1024];
int s[128][1024];
int profit[128][128];
long long d1[128][128];
long long d2[128][128];
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++){
			scanf("%d%d",&b[i][j],&s[i][j]);
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int l = 1; l <= k; l++){
				if(b[i][l] != -1 && s[j][l] != -1){
					profit[i][j] = max(profit[i][j],s[j][l] - b[i][l]);
				}
			}
			d1[i][j] = 1e18;
		}
	}
	for(int i = 1; i <= m; i++){
		int v,w,t;
		scanf("%d%d%d",&v,&w,&t);
		d1[v][w] = t;
	}
	for(int l = 1; l <= n; l++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				d1[i][j] = min(d1[i][j],d1[i][l] + d1[l][j]);
			}
		}
	}
	long long lo = 0ll;
	long long hi = 1e9;
	long long mid;
	while(lo < hi){
		mid = (lo + hi + 1ll)/2ll;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				d2[i][j] = profit[i][j] - mid*min((long long)5e18/mid,d1[i][j]);
			}
		}
		for(int l = 1; l <= n; l++){
			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++){
					d2[i][j] = max(d2[i][j],d2[i][l] + d2[l][j]);
				}
			}
		}
		bool ok = false;
		for(int i = 1; i <= n; i++){
			if(d2[i][i] >= 0){
				ok = true;
			}
		}
		if(ok){
			lo = mid;
		}else{
			hi = mid-1ll;
		}
	}
	printf("%lld\n",lo);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:10: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:13:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&b[i][j],&s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&v,&w,&t);
   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1528 KB Output is correct
2 Correct 43 ms 1532 KB Output is correct
3 Correct 48 ms 1608 KB Output is correct
4 Correct 9 ms 1608 KB Output is correct
5 Correct 8 ms 1608 KB Output is correct
6 Correct 8 ms 1608 KB Output is correct
7 Correct 9 ms 1608 KB Output is correct
8 Correct 2 ms 1608 KB Output is correct
9 Correct 8 ms 1608 KB Output is correct
10 Correct 8 ms 1608 KB Output is correct
11 Correct 8 ms 1608 KB Output is correct
12 Correct 2 ms 1608 KB Output is correct
13 Incorrect 9 ms 1608 KB Output isn't correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1608 KB Output is correct
2 Correct 8 ms 1608 KB Output is correct
3 Correct 9 ms 1608 KB Output is correct
4 Correct 8 ms 1608 KB Output is correct
5 Correct 9 ms 1608 KB Output is correct
6 Correct 2 ms 1608 KB Output is correct
7 Incorrect 8 ms 1608 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1672 KB Output is correct
2 Correct 105 ms 1708 KB Output is correct
3 Correct 46 ms 1708 KB Output is correct
4 Correct 50 ms 1708 KB Output is correct
5 Correct 53 ms 1708 KB Output is correct
6 Correct 47 ms 1800 KB Output is correct
7 Correct 10 ms 1800 KB Output is correct
8 Correct 2 ms 1800 KB Output is correct
9 Correct 9 ms 1800 KB Output is correct
10 Correct 10 ms 1800 KB Output is correct
11 Incorrect 11 ms 1800 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1608 KB Output is correct
2 Correct 8 ms 1608 KB Output is correct
3 Correct 9 ms 1608 KB Output is correct
4 Correct 8 ms 1608 KB Output is correct
5 Correct 9 ms 1608 KB Output is correct
6 Correct 2 ms 1608 KB Output is correct
7 Incorrect 8 ms 1608 KB Output isn't correct
8 Halted 0 ms 0 KB -