Submission #759292

#	Time	Username	Problem	Language	Result	Execution time	Memory
759292		vjudge1	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	950 ms	2852 KiB

merchant

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define X(z) x[z][i][j]
#define L F(i,n)F(j,n)
#define F(x,y) for(int x=1;x<=y;++x)
using namespace std;
int n,m,K,x[4][201][1001];
bool C(int t) {
    L X(3)=-1e18;
    L {
        if(i==j||X(0)>1e9)continue;
        X(3)=-t*X(0);
        F(k,K) {
            if(x[1][i][k]<0||x[2][j][k]<0)continue;
            X(3)=max(X(3),x[2][j][k]-x[1][i][k]-t*X(0));
        }
    }
    F(k,n)L X(3)=max(X(3),x[3][i][k]+x[3][k][j]);
    F(i,n) if(x[3][i][i]>=0)return 1;
    return 0;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> K;
    L X(0)=2e9;
    F(i,n)F(j,K)cin>>X(1)>>X(2);
    F(k,m){
        int i,j,c;
        cin>>i>>j>>c;
        X(0)=min(X(0),c);
    }
    F(k,n)L X(0)=min(X(0),x[0][i][k]+x[0][k][j]);
    int l=0,r=1e9;
    while(l<r-1){
        if(C(l+r>>1)) l=l+r>>1;
        else r=l+r>>1;
    }
    cout << l<< '\n';
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         if(C(l+r>>1)) l=l+r>>1;
      |              ~^~
merchant.cpp:37:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         if(C(l+r>>1)) l=l+r>>1;
      |                         ~^~
merchant.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         else r=l+r>>1;
      |                ~^~

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