제출 #401731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401731		A_D	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	131 ms	105752 KiB

merchant

#include <bits/stdc++.h>

#define int long long
using namespace std;
const int N=51;
// dp start_node time item node
int dp[N][N][N][N];
int b[N][N];
int s[N][N];
vector<int> g[N];
void solve()
{
    int n,m,k;
    scanf("%lld",&n);
    scanf("%lld",&m);
    scanf("%lld",&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            scanf("%lld",&b[i][j]);
            scanf("%lld",&s[i][j]);
        }
    }
    while(m--){
        int u,v,w;
        scanf("%lld",&u);
        scanf("%lld",&v);
        scanf("%lld",&w);
        g[u].push_back(v);
    }
    for(int start=1;start<=n;start++){
        for(int time=0;time<=n;time++){
            for(int item=0;item<=n;item++){
                for(int node=1;node<=n;node++){
                    if(start==node&&time==0&&item==0)continue;
                    dp  [start][time][item][node]  =-1e18;
                }
            }
        }
    }
    for(int start=1;start<=n;start++){
        for(int time=0;time<=n;time++){
            for(int item=1;item<=n;item++){
                for(int node=1;node<=n;node++){
                    if(b[node][item]!=-1)dp[start][time][item][node]=max(dp[start][time][item][node],dp[start][time][0][node]-b[node][item]);
                    for(auto nxt:g[node]){
                        dp[start][time+1][item][nxt]=max(dp[start][time+1][item][nxt],dp[start][time][item][node]);
                        if(s[nxt][item]!=-1)dp[start][time+1][0][nxt]=max(dp[start][time+1][0][nxt],dp[start][time+1][item][nxt]+s[nxt][item]);
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
//            cout<<i<<" "<<j<<" "<<dp[i][j][0][i]<<"\n";
            ans=max(ans,dp[i][j][0][i]/j);
        }
    }
    cout<<ans<<endl;
}

main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main()
      | ^~~~
merchant.cpp: In function 'void solve()':
merchant.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
merchant.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%lld",&m);
      |     ~~~~~^~~~~~~~~~~
merchant.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%lld",&k);
      |     ~~~~~^~~~~~~~~~~
merchant.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |             scanf("%lld",&b[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
merchant.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |             scanf("%lld",&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
merchant.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%lld",&u);
      |         ~~~~~^~~~~~~~~~~
merchant.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%lld",&v);
      |         ~~~~~^~~~~~~~~~~
merchant.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%lld",&w);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34