# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
262493 | 2020-08-13T01:41:42 Z | daniel920712 | 여행하는 상인 (APIO17_merchant) | C++14 | 34 ms | 11384 KB |
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <utility> #include <string.h> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; vector < pair < long long , long long > > Next[200005]; vector < pair < long long , long long > > last[200005]; long long S[105][1005]; long long B[105][1005]; long long in[105]={0}; long long out[105]={0}; bool have[105]; priority_queue < pair < long long , long long > , vector < pair < long long , long long > > , greater < pair < long long , long long > > > all; int main() { long long N,M,K,a,b,c,ans=0,i,j,k; scanf("%lld %lld %lld",&N,&M,&K); for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]); while(M--) { scanf("%lld %lld %lld",&a,&b,&c); Next[a].push_back(make_pair(b,c)); last[b].push_back(make_pair(a,c)); } for(i=1;i<=N;i++) have[i]=0; all.push(make_pair(0,1)); while(!all.empty()) { if(have[all.top().second]) { all.pop(); continue; } have[all.top().second]=1; in[all.top().second]=all.top().first; for(auto i:Next[all.top().second]) all.push(make_pair(all.top().first+i.second,i.first)); all.pop(); } for(i=1;i<=N;i++) have[i]=0; all.push(make_pair(0,1)); while(!all.empty()) { if(have[all.top().second]) { all.pop(); continue; } have[all.top().second]=1; out[all.top().second]=all.top().first; for(auto i:last[all.top().second]) all.push(make_pair(all.top().first+i.second,i.first)); all.pop(); } for(i=2;i<=N;i++) { //printf("%lld %lld\n",in[i],out[i]); for(j=1;j<=K;j++) { if(in[i]&&out[i]&&S[i][j]!=-1&&B[1][j]!=-1) { //printf("%lld %lld %lld %lld\n",i,j,S[i][j],B[1][j]); ans=max(ans,(S[i][j]-B[1][j])/(in[i]+out[i])); } } } printf("%lld\n",ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 11384 KB | Output is correct |
2 | Correct | 8 ms | 10496 KB | Output is correct |
3 | Correct | 7 ms | 10496 KB | Output is correct |
4 | Correct | 7 ms | 10112 KB | Output is correct |
5 | Correct | 7 ms | 10240 KB | Output is correct |
6 | Correct | 8 ms | 10112 KB | Output is correct |
7 | Correct | 9 ms | 10240 KB | Output is correct |
8 | Correct | 6 ms | 9728 KB | Output is correct |
9 | Correct | 7 ms | 10112 KB | Output is correct |
10 | Correct | 8 ms | 10112 KB | Output is correct |
11 | Correct | 7 ms | 10112 KB | Output is correct |
12 | Correct | 6 ms | 9856 KB | Output is correct |
13 | Correct | 8 ms | 10240 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 10112 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 10752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 8 ms | 10112 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |