Submission #365204

#	Time	Username	Problem	Language	Result	Execution time	Memory
365204		YJU	여행하는 상인 (APIO17_merchant)	C++14	100 / 100	97 ms	5612 KiB

merchant

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e3+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
 
ll n,x,y,c,dp[N],val[N][N],dis[N][N],vis[N],m,k,sell[N][N],buy[N][N];
 
ll DIS[N][N];
 
bool ck(ll t){
	REP1(i,n)REP1(j,n)DIS[i][j]=(i==j||dis[i][j]==INF?-INF:val[i][j]-t*dis[i][j]);
	
	REP1(ii,n)REP1(i,n)REP1(j,n)DIS[i][j]=min(INF,max(DIS[i][j],DIS[i][ii]+DIS[ii][j]));
	REP1(i,n)REP1(j,n)if(i!=j&&DIS[i][j]+DIS[j][i]>=0)return 1;
	return 0;
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>k;
	REP1(i,n)REP1(j,n)dis[i][j]=(i==j?0:INF);
	REP1(i,n)REP1(j,k)cin>>buy[i][j]>>sell[i][j];
	REP(i,m){
		cin>>x>>y>>c;
		dis[x][y]=min(dis[x][y],c);
	}
	for(int ii=1;ii<=n;ii++){
		REP1(i,n)REP1(j,n){
			dis[i][j]=min(dis[i][j],dis[i][ii]+dis[ii][j]);
		}
	}
	REP1(i,n)REP1(j,n){
		REP1(ii,k){
			val[i][j]=max(val[i][j],(buy[i][ii]!=-1&&sell[j][ii]!=-1?sell[j][ii]-buy[i][ii]:0));
		}
	}
	/*
	cout<<"dis\n";
	REP1(i,n)REP1(j,n)cout<<dis[i][j]<<(j==n?"\n":" ");
	cout<<"val\n";
	REP1(i,n)REP1(j,n)cout<<val[i][j]<<(j==n?"\n":" ");
	*/
	ll ans=0;
	for(int i=30;i>=0;i--){
		if(ck(ans+(1LL<<i)))ans+=(1LL<<i);
	}
	cout<<ans<<"\n";
	return 0;
}

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