Submission #417272

#	Time	Username	Problem	Language	Result	Execution time	Memory
417272		jamezzz	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	845 ms	418760 KiB

worst_reporter2

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define INF 1023456789123456789
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef long long ll;

int n,a[200005],h[200005],c[200005];
ll m[5005][5005];
vector<int> AL[200005];

ll dp(int u,int p){ //modifed everything after p, before i
	if(m[u][p]!=-1)return m[u][p];
	ll res=INF;
	if(h[p]<=h[u]){ //dont need to modify
		ll tmp=0;
		for(int v:AL[u])tmp+=dp(v,u);
		res=min(res,tmp);
	}
	ll tmp=c[u];
	for(int v:AL[u])tmp+=dp(v,p);
	res=min(res,tmp);
	return m[u][p]=res;
}

int main(){
	sf("%d",&n);
	for(int i=1;i<=n;++i){
		sf("%d%d%d",&a[i],&h[i],&c[i]);
		if(i!=1)AL[a[i]].pb(i);
	}
	memset(m,-1,sizeof m);
	pf("%lld\n",dp(1,0));
}

/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771
*/

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:33:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  sf("%d",&n);
      |    ^
worst_reporter2.cpp:35:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   sf("%d%d%d",&a[i],&h[i],&c[i]);
      |     ^

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