Submission #417184

#	Time	Username	Problem	Language	Result	Execution time	Memory
417184		maomao90	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	1890 ms	197844 KiB

worst_reporter2

#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb emplace_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 5005

int n;
int h[MAXN], c[MAXN];
vi adj[MAXN];
ll memo[MAXN][MAXN];

ll dp(int u, int ptake, int p) {
	if (memo[u][ptake] != -1) return memo[u][ptake];
	int pv = -1;
	if (ptake != -1) {
		pv = h[ptake];
	}
	vector<ll> notake, take;
	for (int v : adj[u]) {
		notake.pb(dp(v, u, u));
		take.pb(dp(v, ptake, u));
	}
	ll notakev = 0, takev = c[u];
	REP (i, 0, notake.size()) {
		notakev += notake[i];
		takev += take[i];
	}
	//printf("%d: %lld %lld\n", u, notakev, takev);
	if (pv > h[u]) {
		return memo[u][ptake] = takev;
	}
	return memo[u][ptake] = min(takev, notakev);
}

int main() {
	scanf("%d", &n);
	REP (i, 1, n + 1) {
		int a; scanf("%d%d%d", &a, &h[i], &c[i]);
		if (i != 1) adj[a].pb(i);
	}
	memset(memo, -1, sizeof memo);
	printf("%lld\n", dp(1, -1, -1));
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'll dp(int, int, int)':
worst_reporter2.cpp:8:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define REP(i, s, e) for (int i = s; i < e; i++)
......
   47 |  REP (i, 0, notake.size()) {
      |       ~~~~~~~~~~~~~~~~~~~               
worst_reporter2.cpp:47:2: note: in expansion of macro 'REP'
   47 |  REP (i, 0, notake.size()) {
      |  ^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:61:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   int a; scanf("%d%d%d", &a, &h[i], &c[i]);
      |          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21