Submission #19336192


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define MAX 9223372036854775807
#define MIN -9223372036854775807
#define PI 3.141592653589
#define setbits(n) __builtin_popcountll(n)
#define mkunique(a) a.resize(unique(a.begin(),a.end())-a.begin());
const ll mod=1e9+7;


const int N=2e5+10;
vector<ll> a[N];
vector<ll> v(N);
ll ans=-mod*mod;
vector<ll> dp(N);
vector<bool> vis(N);

ll dfs(ll i, ll mn=mod){
    vis[i]=true;
    mn=min(mn,v[i]);
    ll mx=-mod;
    for(ll u: a[i]){
        if(vis[u])
            mx=max(mx,dp[u]);
        else
            mx=max(mx,dfs(u,mn));
    }
    ans=max(ans,mx-mn);
    return dp[i]=max(mx,v[i]);
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll T=clock();
 
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++)
        cin>>v[i];
    for(ll i=0;i<m;i++){
        ll u,v;
        cin>>u>>v; u--,v--;
        a[u].pb(v);
    }
    for(ll i=0;i<n;i++){
        if(!vis[i])
            dfs(i);
    }
    cout<<ans;
    
    
    cerr<<"\n\nTIME: "<<(double)(clock()-T)/CLOCKS_PER_SEC<<" sec\n";
    T = clock();
    return 0;
}

Submission Info

Submission Time
Task E - Peddler
User sharath101
Language C++ (GCC 9.2.1)
Score 500
Code Size 1293 Byte
Status AC
Exec Time 115 ms
Memory 36084 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 115 ms 36084 KB
extreme_01.txt AC 64 ms 13196 KB
extreme_02.txt AC 63 ms 15180 KB
extreme_03.txt AC 34 ms 10984 KB
handmade_00.txt AC 15 ms 10956 KB
handmade_01.txt AC 12 ms 10780 KB
random_00.txt AC 63 ms 13168 KB
random_01.txt AC 76 ms 14224 KB
random_02.txt AC 42 ms 13536 KB
random_03.txt AC 39 ms 12136 KB
random_04.txt AC 36 ms 12992 KB
random_05.txt AC 33 ms 10820 KB
random_06.txt AC 22 ms 11736 KB
random_07.txt AC 50 ms 13020 KB
random_08.txt AC 61 ms 14036 KB
random_09.txt AC 50 ms 12164 KB
random_10.txt AC 34 ms 12140 KB
random_11.txt AC 75 ms 13968 KB
random_12.txt AC 44 ms 12496 KB
random_13.txt AC 67 ms 13452 KB
random_14.txt AC 48 ms 12664 KB
random_15.txt AC 80 ms 14232 KB
random_16.txt AC 49 ms 12972 KB
random_17.txt AC 82 ms 14240 KB
random_18.txt AC 15 ms 10832 KB
random_19.txt AC 52 ms 12404 KB
random_dense_00.txt AC 24 ms 12424 KB
random_dense_01.txt AC 36 ms 13192 KB
random_dense_02.txt AC 37 ms 13192 KB
random_dense_03.txt AC 33 ms 13024 KB
random_dense_04.txt AC 11 ms 10816 KB
random_dense_05.txt AC 22 ms 11800 KB
random_dense_06.txt AC 39 ms 13456 KB
random_dense_07.txt AC 13 ms 10904 KB
random_dense_08.txt AC 38 ms 13812 KB
random_dense_09.txt AC 21 ms 11608 KB
random_small_00.txt AC 11 ms 10936 KB
random_small_01.txt AC 15 ms 10832 KB
random_small_02.txt AC 12 ms 10908 KB
random_small_03.txt AC 17 ms 10848 KB
random_small_04.txt AC 13 ms 10896 KB
random_small_05.txt AC 11 ms 10940 KB
random_small_06.txt AC 11 ms 10816 KB
random_small_07.txt AC 14 ms 10932 KB
random_small_08.txt AC 14 ms 10832 KB
random_small_09.txt AC 16 ms 10812 KB
sample_01.txt AC 9 ms 10932 KB
sample_02.txt AC 13 ms 10956 KB
sample_03.txt AC 10 ms 10816 KB