답안 #402770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402770	2021-05-12T10:48:26 Z	Hazem	여행하는 상인 (APIO17_merchant)	C++14	100 / 100	109 ms	5168 KB

merchant

#include <bits/stdc++.h>
using namespace std;
 
#define LL long long
#define F first
#define S second
#define pii pair<int,int>
#define piii pair<pair<int,int>,int>

const int N = 2e5+10;
const int M = 200;
const LL INF = 1e9;
const LL LINF = 1e14;
const LL MOD = 1e9+7;
const double PI = 3.141592653589793;

LL s[M][M*10],b[M][M*10];
LL dis[M][M],profit[M][M],dis1[M][M];

int main(){

    //freopen("out.txt","w",stdout);

    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("%lld%lld",&b[i][j],&s[i][j]);

    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v] = w;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!dis[i][j])
                dis[i][j] = LINF;

    for(int k1=1;k1<=n;k1++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j] = min(dis[i][j],dis[i][k1]+dis[k1][j]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int j1=1;j1<=k;j1++)
                if(b[i][j1]!=-1&&s[j][j1]!=-1)
                    profit[i][j] = max(profit[i][j],s[j][j1]-b[i][j1]);

    LL l = 0,r = 1e9;
    while(l<r){

        int mid = (l+r+1)/2;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(dis[i][j]!=LINF)
                    dis1[i][j] = dis[i][j]*mid-profit[i][j];
                else 
                    dis1[i][j] = LINF;
        
        for(int k1=1;k1<=n;k1++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    dis1[i][j] = min(dis1[i][j],dis1[i][k1]+dis1[k1][j]);

        bool q = 0;
        for(int i=1;i<=n;i++)
            q |= dis1[i][i]<=0;

        if(q)l = mid;
        else r = mid-1;
    }

    printf("%lld\n",l);
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:29:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |             scanf("%lld%lld",&b[i][j],&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d%d%d",&u,&v,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	73 ms	2916 KB	Output is correct
2	Correct	39 ms	1356 KB	Output is correct
3	Correct	40 ms	1356 KB	Output is correct
4	Correct	6 ms	872 KB	Output is correct
5	Correct	9 ms	872 KB	Output is correct
6	Correct	6 ms	844 KB	Output is correct
7	Correct	7 ms	844 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	6 ms	844 KB	Output is correct
10	Correct	7 ms	888 KB	Output is correct
11	Correct	7 ms	832 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	7 ms	828 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	844 KB	Output is correct
2	Correct	7 ms	844 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	6 ms	844 KB	Output is correct
5	Correct	7 ms	888 KB	Output is correct
6	Correct	7 ms	832 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	7 ms	828 KB	Output is correct
9	Correct	7 ms	844 KB	Output is correct
10	Correct	6 ms	844 KB	Output is correct
11	Correct	7 ms	952 KB	Output is correct
12	Correct	7 ms	972 KB	Output is correct
13	Correct	8 ms	952 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	7 ms	948 KB	Output is correct
16	Correct	7 ms	972 KB	Output is correct
17	Correct	7 ms	844 KB	Output is correct
18	Correct	10 ms	980 KB	Output is correct
19	Correct	7 ms	972 KB	Output is correct
20	Correct	10 ms	1024 KB	Output is correct
21	Correct	8 ms	972 KB	Output is correct
22	Correct	9 ms	972 KB	Output is correct
23	Correct	8 ms	952 KB	Output is correct
24	Correct	7 ms	808 KB	Output is correct
25	Correct	8 ms	1008 KB	Output is correct
26	Correct	1 ms	296 KB	Output is correct
27	Correct	8 ms	1032 KB	Output is correct
28	Correct	8 ms	972 KB	Output is correct
29	Correct	8 ms	972 KB	Output is correct
30	Correct	9 ms	968 KB	Output is correct
31	Correct	7 ms	844 KB	Output is correct

Subtask #3
33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	1008 KB	Output is correct
2	Correct	1 ms	296 KB	Output is correct
3	Correct	8 ms	1032 KB	Output is correct
4	Correct	8 ms	972 KB	Output is correct
5	Correct	8 ms	972 KB	Output is correct
6	Correct	9 ms	968 KB	Output is correct
7	Correct	7 ms	844 KB	Output is correct
8	Correct	46 ms	1712 KB	Output is correct
9	Correct	101 ms	4672 KB	Output is correct
10	Correct	58 ms	1612 KB	Output is correct
11	Correct	46 ms	1920 KB	Output is correct
12	Correct	61 ms	1920 KB	Output is correct
13	Correct	43 ms	1612 KB	Output is correct

Subtask #4
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	844 KB	Output is correct
2	Correct	6 ms	844 KB	Output is correct
3	Correct	7 ms	952 KB	Output is correct
4	Correct	7 ms	972 KB	Output is correct
5	Correct	8 ms	952 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	7 ms	948 KB	Output is correct
8	Correct	7 ms	972 KB	Output is correct
9	Correct	7 ms	844 KB	Output is correct
10	Correct	10 ms	980 KB	Output is correct
11	Correct	7 ms	972 KB	Output is correct
12	Correct	10 ms	1024 KB	Output is correct
13	Correct	8 ms	972 KB	Output is correct
14	Correct	9 ms	972 KB	Output is correct
15	Correct	8 ms	952 KB	Output is correct
16	Correct	7 ms	808 KB	Output is correct
17	Correct	46 ms	1712 KB	Output is correct
18	Correct	101 ms	4672 KB	Output is correct
19	Correct	58 ms	1612 KB	Output is correct
20	Correct	46 ms	1920 KB	Output is correct
21	Correct	61 ms	1920 KB	Output is correct
22	Correct	43 ms	1612 KB	Output is correct
23	Correct	8 ms	1008 KB	Output is correct
24	Correct	1 ms	296 KB	Output is correct
25	Correct	8 ms	1032 KB	Output is correct
26	Correct	8 ms	972 KB	Output is correct
27	Correct	8 ms	972 KB	Output is correct
28	Correct	9 ms	968 KB	Output is correct
29	Correct	7 ms	844 KB	Output is correct
30	Correct	73 ms	2916 KB	Output is correct
31	Correct	39 ms	1356 KB	Output is correct
32	Correct	40 ms	1356 KB	Output is correct
33	Correct	6 ms	872 KB	Output is correct
34	Correct	9 ms	872 KB	Output is correct
35	Correct	6 ms	844 KB	Output is correct
36	Correct	7 ms	844 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	6 ms	844 KB	Output is correct
39	Correct	7 ms	888 KB	Output is correct
40	Correct	7 ms	832 KB	Output is correct
41	Correct	1 ms	332 KB	Output is correct
42	Correct	7 ms	828 KB	Output is correct
43	Correct	41 ms	1576 KB	Output is correct
44	Correct	44 ms	1720 KB	Output is correct
45	Correct	66 ms	3312 KB	Output is correct
46	Correct	43 ms	1740 KB	Output is correct
47	Correct	45 ms	1788 KB	Output is correct
48	Correct	45 ms	1716 KB	Output is correct
49	Correct	105 ms	5080 KB	Output is correct
50	Correct	1 ms	332 KB	Output is correct
51	Correct	1 ms	332 KB	Output is correct
52	Correct	56 ms	1468 KB	Output is correct
53	Correct	44 ms	1620 KB	Output is correct
54	Correct	42 ms	1612 KB	Output is correct
55	Correct	41 ms	1484 KB	Output is correct
56	Correct	42 ms	1608 KB	Output is correct
57	Correct	1 ms	332 KB	Output is correct
58	Correct	9 ms	1116 KB	Output is correct
59	Correct	9 ms	1116 KB	Output is correct
60	Correct	12 ms	1080 KB	Output is correct
61	Correct	107 ms	5164 KB	Output is correct
62	Correct	109 ms	5168 KB	Output is correct
63	Correct	1 ms	332 KB	Output is correct

답안 #402770

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 21.0 / 21.0

Subtask #3 33.0 / 33.0

Subtask #4 34.0 / 34.0

Subtask #1
12.0 / 12.0

Subtask #2
21.0 / 21.0

Subtask #3
33.0 / 33.0

Subtask #4
34.0 / 34.0