Submission #19370509


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 7;
const ll mod = 1000000007;

#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)


ll read() {
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
void out(ll x) {
	int stackk[40];
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (!x) {
		putchar('0');
		return;
	}
	int top = 0;
	while (x) stackk[++top] = x % 10, x /= 10;
	while (top) putchar(stackk[top--] + '0');
}
int n,m,val[maxn],dp[maxn],in[maxn];
vector<int>e[maxn];
int ans=-inf,vis[maxn],mi[maxn];
void work() {
	queue<int>q;

	rep(i,1,n) if(in[i]==0) q.push(i),mi[i] = val[i];
	while(q.size()) {

		int fr = q.front();
		q.pop();
	
		for(int v:e[fr]) {
			
			dp[v] = max(dp[v],val[v]-mi[fr]);
			ans = max(ans,dp[v]);
			mi[v] = min(mi[fr],val[v]);
			in[v]--;
			if(in[v]==0)	q.push(v);

		}
	}
	out(ans);
}

int main() {
	n=read(),m=read();
	rep(i,1,n) val[i] = read(),dp[i] = -inf,mi[i] = inf;
	for(int i=1 ; i<=m ; i++) {
		int u,v;
		u=read(),v=read();
		e[u].push_back(v);
		in[v] ++;
	}
	work();
	return 0;
}
/**


**/


Submission Info

Submission Time
Task E - Peddler
User UpMing
Language C++ (GCC 9.2.1)
Score 0
Code Size 1461 Byte
Status WA
Exec Time 69 ms
Memory 17548 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 42
WA × 7
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 69 ms 17548 KB
extreme_01.txt AC 38 ms 12544 KB
extreme_02.txt WA 34 ms 14528 KB
extreme_03.txt AC 24 ms 11064 KB
handmade_00.txt AC 10 ms 8180 KB
handmade_01.txt AC 8 ms 8180 KB
random_00.txt AC 40 ms 13136 KB
random_01.txt WA 51 ms 13060 KB
random_02.txt WA 23 ms 9544 KB
random_03.txt AC 26 ms 10788 KB
random_04.txt WA 18 ms 9288 KB
random_05.txt AC 20 ms 11220 KB
random_06.txt WA 12 ms 8632 KB
random_07.txt AC 34 ms 12196 KB
random_08.txt WA 39 ms 10732 KB
random_09.txt AC 34 ms 12648 KB
random_10.txt AC 19 ms 9876 KB
random_11.txt AC 49 ms 13536 KB
random_12.txt AC 30 ms 11128 KB
random_13.txt AC 47 ms 13752 KB
random_14.txt AC 27 ms 11004 KB
random_15.txt AC 52 ms 13928 KB
random_16.txt AC 35 ms 11064 KB
random_17.txt AC 55 ms 14416 KB
random_18.txt AC 12 ms 9008 KB
random_19.txt AC 38 ms 12724 KB
random_dense_00.txt AC 14 ms 8912 KB
random_dense_01.txt AC 19 ms 9448 KB
random_dense_02.txt AC 16 ms 9220 KB
random_dense_03.txt AC 16 ms 9052 KB
random_dense_04.txt AC 8 ms 8120 KB
random_dense_05.txt AC 10 ms 8552 KB
random_dense_06.txt AC 18 ms 9096 KB
random_dense_07.txt AC 12 ms 8212 KB
random_dense_08.txt AC 23 ms 9284 KB
random_dense_09.txt WA 12 ms 8520 KB
random_small_00.txt AC 8 ms 8128 KB
random_small_01.txt AC 7 ms 8132 KB
random_small_02.txt AC 11 ms 8092 KB
random_small_03.txt AC 7 ms 8088 KB
random_small_04.txt AC 10 ms 8280 KB
random_small_05.txt AC 12 ms 8128 KB
random_small_06.txt AC 6 ms 8176 KB
random_small_07.txt AC 8 ms 8208 KB
random_small_08.txt AC 10 ms 8216 KB
random_small_09.txt AC 7 ms 8184 KB
sample_01.txt AC 8 ms 8132 KB
sample_02.txt AC 11 ms 8260 KB
sample_03.txt AC 7 ms 8132 KB