Submission #403533

#	Time	Username	Problem	Language	Result	Execution time	Memory
403533		A_D	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	57 ms	1416 KiB

merchant

#include <bits/stdc++.h>
 
#define int long long
using namespace std;
const int N=52;
// dp start_node time item node
int dp[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);
    if(n>50)return;
    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);
    }
    int ans=0;
    for(int start=1;start<=n;start++){
        for(int time=0;time<=n;time++){
            for(int item=0;item<=k;item++){
                for(int node=1;node<=n;node++){
                    if(start==node&&time==0&&item==0){
                        dp  [time][item][node]  =0;
                    }
                    else{
                        dp  [time][item][node]  =-1e18;
                    }
                }
            }
        }
        for(int time=0;time<=n;time++){
            for(int item=0;item<=k;item++){
                for(int node=1;node<=n;node++){
                    if(b[node][item]!=-1)dp[time][item][node]=max(dp[time][item][node],dp[time][0][node]-b[node][item]);
                }
            }
            for(int item=0;item<=k;item++){
                for(int node=1;node<=n;node++){
                    for(auto nxt:g[node]){
                        dp[time+1][item][nxt]=max(dp[time+1][item][nxt],dp[time][item][node]);
                        if(s[nxt][item]!=-1)dp[time+1][0][nxt]=max(dp[time+1][0][nxt],dp[time+1][item][nxt]+s[nxt][item]);
                    }
                }
            }
        }
        for(int time=1;time<=n;time++){
            ans=max(ans,dp[time][0][start]/time);
        }
    }
    cout<<ans<<endl;
}
 
main()
{
    int t=1;
//    cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

merchant.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | 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:20:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |             scanf("%lld",&b[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
merchant.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |             scanf("%lld",&s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
merchant.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%lld",&u);
      |         ~~~~~^~~~~~~~~~~
merchant.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%lld",&v);
      |         ~~~~~^~~~~~~~~~~
merchant.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%lld",&w);
      |         ~~~~~^~~~~~~~~~~

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