Submission #19381282


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define setbits(x)      __builtin_popcountll(x)
#define leadzero(x)     __builtin_clz(x)
#define trailzero(x)    __builtin_ctz(x)
#define mod             1000000007
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll              long long 
#define int             ll
#define ld              long double
#define ff              first
#define ss              second
#define pb              push_back
#define eb              emplace_back
#define popb            pop_back
#define endl            '\n'
#define all(v)          v.begin(), v.end()
#define sz(x)           ((int)((x).size()))
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pii> vii;
typedef vector<pll> vll; 
typedef vector<ll> vl; 
typedef vector<vl> vvl;
typedef vector<string> vs;
ll power(ll a, ll b) {
    if(b<0) return 1;
    ll res=1;
    while(b) {
        if(b&1) 
            res = (res*a);//%mod;
        a = (a*a);//%mod;
        b >>= 1;
    }
    return res;
}
template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
bool ispoweroftwo(ll x){ return (x&&!(x&(x-1)));}
ll GCD(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
ll LCM(ll a, ll b) {return a / GCD(a, b) * b;}
const int inf = 1e9;
const ll INF = 1e18;
const ld pi = 3.141592653589793238;
int dx[] = {-1, 0, 1, 0}; 
int dy[] = {0, 1, 0, -1};
char MV[] = {'U', 'R', 'D', 'L'};
//Shoot for the moon - If you miss, you'll end up in the stars
//integer to char always remember (char+'0')
//----------------------------------------------------------------------------------------
const int mxn = 2e5 + 9;
vector<int> g[mxn];
int n, m;
int dp[mxn], a[mxn], vis[mxn];
//dp[i] represents the cheapest price of gold of a city, which we wanna purchase the gold from and sell it at the 
//current city(except the current city)


//buying the gold from other city and selling at current city 
//then ans will be max(price of gold at current city(i) - dp[i])

void dfs(int v) {
    vis[v] = 1;
    for (int u: g[v]) {
        if(!vis[u]) {
            dp[u] = min({dp[v], a[v], dp[u]});
            dfs(u);
        } 
        else {
            //if already visited then we need to check if our answer is getting minimized or not
            int prev = dp[u];
            dp[u] = min({dp[v], a[v], dp[u]});
            //if so then we will again do dfs with this min price of gold 
            if(dp[u] != prev)
                dfs(u);
        }
    }
}
int32_t main() {
    FIO;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    cin >> n >> m;

    for(int i = 1; i <= n; ++i) cin >> a[i], dp[i] = INF;
    for (int i = 0; i < m; ++i) {
        int x, y; cin >> x >> y;
        g[x].pb(y);
    }

    for (int i = 1; i <= n; ++i) {
        if(!vis[i]) {
            dfs(i);
        }
    }
    int ans = -INF;

    for (int i = 1; i <= n; ++i) {
        ans = max(ans, a[i] - dp[i]);
    } 
    cout << ans;
    return 0;
}

Submission Info

Submission Time
Task E - Peddler
User rum3r
Language C++ (GCC 9.2.1)
Score 500
Code Size 3570 Byte
Status AC
Exec Time 109 ms
Memory 31628 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All extreme_00.txt, extreme_01.txt, extreme_02.txt, extreme_03.txt, handmade_00.txt, handmade_01.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_dense_00.txt, random_dense_01.txt, random_dense_02.txt, random_dense_03.txt, random_dense_04.txt, random_dense_05.txt, random_dense_06.txt, random_dense_07.txt, random_dense_08.txt, random_dense_09.txt, random_small_00.txt, random_small_01.txt, random_small_02.txt, random_small_03.txt, random_small_04.txt, random_small_05.txt, random_small_06.txt, random_small_07.txt, random_small_08.txt, random_small_09.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
extreme_00.txt AC 109 ms 31628 KB
extreme_01.txt AC 60 ms 14180 KB
extreme_02.txt AC 73 ms 16556 KB
extreme_03.txt AC 30 ms 12872 KB
handmade_00.txt AC 9 ms 8152 KB
handmade_01.txt AC 11 ms 8160 KB
random_00.txt AC 64 ms 14428 KB
random_01.txt AC 76 ms 14296 KB
random_02.txt AC 43 ms 10780 KB
random_03.txt AC 34 ms 11396 KB
random_04.txt AC 40 ms 10092 KB
random_05.txt AC 34 ms 12056 KB
random_06.txt AC 16 ms 8780 KB
random_07.txt AC 49 ms 12856 KB
random_08.txt AC 64 ms 12108 KB
random_09.txt AC 47 ms 13844 KB
random_10.txt AC 32 ms 10244 KB
random_11.txt AC 71 ms 14676 KB
random_12.txt AC 38 ms 11992 KB
random_13.txt AC 65 ms 15048 KB
random_14.txt AC 46 ms 11696 KB
random_15.txt AC 75 ms 15208 KB
random_16.txt AC 47 ms 11764 KB
random_17.txt AC 78 ms 15844 KB
random_18.txt AC 17 ms 9232 KB
random_19.txt AC 51 ms 13916 KB
random_dense_00.txt AC 25 ms 9304 KB
random_dense_01.txt AC 35 ms 10224 KB
random_dense_02.txt AC 36 ms 10144 KB
random_dense_03.txt AC 34 ms 9824 KB
random_dense_04.txt AC 11 ms 8148 KB
random_dense_05.txt AC 16 ms 8808 KB
random_dense_06.txt AC 38 ms 10320 KB
random_dense_07.txt AC 10 ms 8328 KB
random_dense_08.txt AC 41 ms 10492 KB
random_dense_09.txt AC 18 ms 8804 KB
random_small_00.txt AC 7 ms 8168 KB
random_small_01.txt AC 6 ms 8212 KB
random_small_02.txt AC 7 ms 8264 KB
random_small_03.txt AC 8 ms 8232 KB
random_small_04.txt AC 7 ms 8236 KB
random_small_05.txt AC 7 ms 8160 KB
random_small_06.txt AC 6 ms 8152 KB
random_small_07.txt AC 11 ms 8164 KB
random_small_08.txt AC 7 ms 8168 KB
random_small_09.txt AC 9 ms 8128 KB
sample_01.txt AC 8 ms 8124 KB
sample_02.txt AC 7 ms 8200 KB
sample_03.txt AC 7 ms 8196 KB