Submission #239106

#	Time	Username	Problem	Language	Result	Execution time	Memory
239106		urd05	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	29 ms	1152 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

int buy[100][1000];
int sell[100][1000];
typedef pair<int,int> P;
vector<P> adj[100];
vector<P> rev[100];
long long dist[100];
long long rist[100];
const long long INF=1e15;

int main(void) {
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    for(int i=0;i<n;i++) {
        dist[i]=INF;
        rist[i]=INF;
        for(int j=0;j<k;j++) {
            scanf("%d %d",&buy[i][j],&sell[i][j]);
        }
    }
    for(int i=0;i<m;i++) {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        u--;
        v--;
        adj[u].push_back(P(v,w));
        rev[v].push_back(P(u,w));
    }
    for(int i=0;i<adj[0].size();i++) {
        int nt=adj[0][i].first;
        dist[nt]=adj[0][i].second;
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            for(int k=0;k<adj[j].size();k++) {
                int nt=adj[j][k].first;
                dist[nt]=min(dist[nt],dist[j]+adj[j][k].second);
            }
        }
    }
    rist[0]=0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            for(int k=0;k<rev[j].size();k++) {
                int nt=rev[j][k].first;
                rist[nt]=min(rist[nt],rist[j]+rev[j][k].second);
            }
        }
    }
    long long ret=0;
    for(int i=0;i<n;i++) {
        for(int j=0;j<k;j++) {
            if (sell[i][j]!=-1&&buy[0][j]!=-1)
                ret=max(ret,(sell[i][j]-buy[0][j])/(rist[i]+dist[i]));
        }
    }
    printf("%lld",ret);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[0].size();i++) {
                 ~^~~~~~~~~~~~~~
merchant.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<adj[j].size();k++) {
                         ~^~~~~~~~~~~~~~
merchant.cpp:46:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<rev[j].size();k++) {
                         ~^~~~~~~~~~~~~~
merchant.cpp:15:10: 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:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&buy[i][j],&sell[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&u,&v,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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