oj.uz

Submission #49962

# Submission time Handle Problem Language Result Execution time Memory
49962 2018-06-05T12:43:53 Z hamzqq9 Travelling Merchant (APIO17_merchant) C++14
0 / 100
 104 ms 1664 KB 
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 100000000000000000
#define M 10000002
#define N 105
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) ((1ll)<<(x))
#define PI 3.1415926535
using namespace std;

int n,m,k,x,y,z;
int b[N][N*10],s[N][N*10];
ll p[N][N],d1[N][N],d2[N][N];

bool neg(int pro) {

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			if(d1[i][j]==inf) d2[i][j]=inf;
			else d2[i][j]=1ll*d1[i][j]*pro-p[i][j];

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			for(int k=1;k<=n;k++) {

				umin(d2[j][k],d2[j][i]+d2[i][k]);

			}

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			if(d2[i][j]+d2[j][i]<=0) return true;

		}

	}

	return false;

}

int main() {
 
 	#if 0
	freopen("input.txt","r",stdin);
 	#endif

	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++) {

			d1[i][j]=inf;

		}

	}

	for(int i=1;i<=m;i++) {

		scanf("%d %d %d",&x,&y,&z);

		umin(d1[x][y],1ll*z);

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			for(int k=1;k<=n;k++) {

				umin(d1[j][k],d1[j][i]+d1[i][k]);

			}

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			for(int g=1;g<=k;g++) {

				if(~s[j][g] && ~b[i][g]) {

					umax(p[i][j],1ll*s[j][g]-b[i][g]);
				
				}	
			
			}

		}

	}

	/*for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%d ",p[i][j]);

		printf("\n\n\n\n");

	for(int i=1;i<=n;i++,puts("")) for(int j=1;j<=n;j++) printf("%lld ",d1[i][j]);*/

	int bas=1,son=1e9+5;

	while(bas<=son) {

		if(neg(orta)) bas=orta+1;
		else son=orta-1;

	}

	printf("%d",son);

}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:94: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:100: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:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1272 KB Output is correct
2 Correct 41 ms 1388 KB Output is correct
3 Incorrect 49 ms 1388 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1612 KB Output is correct
2 Correct 104 ms 1664 KB Output is correct
3 Incorrect 46 ms 1664 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

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