Submission #1188994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188994		Malix	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1094 ms	528344 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<ll,ll,ll> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,m,k;
ll X[100][1000],Y[100][1000];
pair<ll,ll> dist[100][1001];
vector<vector<pair<int,ll>>> a;

int main() {   
// ios::sync_with_stdio(0);
// cin.tie(0);
    cin>>n>>m>>k;
    REP(i,0,100)REP(j,0,1001)dist[i][j]={-INF,-INF};
    REP(i,0,n)REP(j,0,k)cin>>X[i][j]>>Y[i][j];
    a.resize(n);
    REP(i,0,m){
        int x,y;cin>>x>>y;
        ll z;cin>>z;
        x--;y--;
        a[x].PB({y,z});
    }
ll ans=0;
REP(r,0,n){
    priority_queue<tuple<double,int,int>> pq;
    REP(i,r,r+1)REP(j,0,k){
        for(auto u:a[i])if(dist[u.F][j].F==-INF||(double)dist[u.F][j].F/(double)dist[u.F][j].F<(double)(-X[i][j])/(double)u.S){
            dist[i][j]={-X[i][j],u.S};
        }
    }
    REP(i,0,n)REP(j,0,k)if(dist[i][j].F!=-INF)pq.push({(double)dist[i][j].F/(double)dist[i][j].S,i,j});
    while(!pq.empty()){
        int x=get<1>(pq.top());
        int y=get<2>(pq.top());
        double z=get<0>(pq.top());
        pq.pop();
        ll p=dist[x][y].F;
        ll q=dist[x][y].S;
        if((double)p/(double)q>z)continue;
        if(y==1000){
            REP(i,0,k)if(X[x][i]!=-1){
                double c=(double)dist[x][i].F/(double)dist[x][i].S;
                double d=(double)(p-X[x][i])/(double)q;
                if(c<0&&d<0){
                    c=abs(c);
                    d=abs(d);
                }
                if(dist[x][i].F==-INF||c<d){
                    dist[x][i]={p-X[x][i],q};
                    pq.push({(double)dist[x][i].F/(double)dist[x][i].S,x,i});
                }
            }
        }
        else{
            if(Y[x][y]!=-1&&p+Y[x][y]>0){
                double c=(double)dist[x][1000].F/(double)dist[x][1000].S;
                double d=(double)(p+Y[x][y]/(double)q);
                if(c<0&&d<0){
                    c=abs(c);
                    d=abs(d);
                }
                if(dist[x][1000].F==-INF||c<d){
                    dist[x][1000]={p+Y[x][y],q};
                    pq.push({(double)dist[x][1000].F/(double)dist[x][1000].S,x,1000});
                }
            }
        }
        for(auto u:a[x]){
            double c=(double)dist[u.F][y].F/(double)dist[u.F][y].S;
            double d=(double)p/(double)(q+u.S);
            if(c<0&&d<0){
                c=abs(c);
                d=abs(d);
            }
            if(dist[u.F][y].F==-INF||c<d){
                dist[u.F][y]={p,q+u.S};
                pq.push({(double)dist[u.F][y].F/(double)dist[u.F][y].S,u.F,y});
            }
        }
    }
    ans=max(ans,dist[r][1000].F/dist[r][1000].S);
}
    cout<<ans;
}

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