Submission #19724232


Source Code Expand

Copy
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i< (n); i++)
using ll = long long;
using namespace std;
using namespace atcoder;

const int inf = 2e9;

int main(){
	int N, M;
	cin >> N >> M;
	vector<int> A(N);
	rep(i,N) cin >> A[i];
	vector<vector<int>> route(N);
	vector<int> in(N);
	rep(i,M) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		in[y]++;
		route[x].push_back(y);
	}
	queue<int> q;
	rep(i,N) {
		if (in[i] == 0) q.push(i);
	}
	vector<int> mina(N, inf);
	int ans = -inf;
	while (!q.empty()) {
		int i = q.front();
		q.pop();
		ans = max(ans, A[i]-mina[i]);
		for (int j : route[i]) {
			in[j]--;
			if(in[j] == 0) q.push(j);
			mina[j] = min(mina[j], mina[i]);
			mina[j] = min(mina[j], A[i]);
		}
	}
	cout << ans << endl;

	return 0;
}

Submission Info

Submission Time
Task E - Peddler
User tsr
Language C++ (GCC 9.2.1)
Score 500
Code Size 822 Byte
Status AC
Exec Time 188 ms
Memory 16408 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 188 ms 16408 KB
extreme_01.txt AC 139 ms 11748 KB
extreme_02.txt AC 156 ms 14084 KB
extreme_03.txt AC 72 ms 11032 KB
handmade_00.txt AC 3 ms 3532 KB
handmade_01.txt AC 2 ms 3628 KB
random_00.txt AC 112 ms 11756 KB
random_01.txt AC 137 ms 10312 KB
random_02.txt AC 73 ms 4760 KB
random_03.txt AC 60 ms 7752 KB
random_04.txt AC 62 ms 4600 KB
random_05.txt AC 64 ms 9528 KB
random_06.txt AC 25 ms 3872 KB
random_07.txt AC 92 ms 9468 KB
random_08.txt AC 110 ms 6560 KB
random_09.txt AC 91 ms 11936 KB
random_10.txt AC 52 ms 5500 KB
random_11.txt AC 138 ms 11580 KB
random_12.txt AC 72 ms 8588 KB
random_13.txt AC 129 ms 12632 KB
random_14.txt AC 83 ms 7264 KB
random_15.txt AC 146 ms 12116 KB
random_16.txt AC 87 ms 7432 KB
random_17.txt AC 153 ms 13128 KB
random_18.txt AC 23 ms 4892 KB
random_19.txt AC 100 ms 11920 KB
random_dense_00.txt AC 39 ms 4188 KB
random_dense_01.txt AC 64 ms 4812 KB
random_dense_02.txt AC 59 ms 4760 KB
random_dense_03.txt AC 55 ms 4544 KB
random_dense_04.txt AC 3 ms 3436 KB
random_dense_05.txt AC 30 ms 3916 KB
random_dense_06.txt AC 66 ms 4660 KB
random_dense_07.txt AC 9 ms 3700 KB
random_dense_08.txt AC 66 ms 4480 KB
random_dense_09.txt AC 27 ms 3924 KB
random_small_00.txt AC 2 ms 3516 KB
random_small_01.txt AC 3 ms 3520 KB
random_small_02.txt AC 2 ms 3460 KB
random_small_03.txt AC 2 ms 3612 KB
random_small_04.txt AC 2 ms 3608 KB
random_small_05.txt AC 2 ms 3516 KB
random_small_06.txt AC 3 ms 3492 KB
random_small_07.txt AC 2 ms 3428 KB
random_small_08.txt AC 2 ms 3560 KB
random_small_09.txt AC 2 ms 3576 KB
sample_01.txt AC 2 ms 3556 KB
sample_02.txt AC 2 ms 3460 KB
sample_03.txt AC 2 ms 3520 KB