Submission #759285

#	Time	Username	Problem	Language	Result	Execution time	Memory
759285		boyliguanhan	Travelling Merchant (APIO17_merchant)	C++17	21 / 100	380 ms	2372 KiB

merchant

#include<bits/stdc++.h>
#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][101][101];
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 >> n >> m >> K;
    L X(0)=2e9;
    F(i,n)F(j,K)cin>>X(1)>>X(2);
    F(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        x[0][a][b]=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){
        if(C(l+r+1>>1)) {
            l = l+r+1>>1;
        } else {
            r = l+r-1>>1;
        }
    }
    cout << l<< '\n';
}

Compilation message (stderr)

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

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