Submission #525036

#	Time	Username	Problem	Language	Result	Execution time	Memory
525036		amunduzbaev	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	14 / 100	199 ms	197152 KiB

worst_reporter2

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

#define ar array
typedef long long ll;
const int N = 5005;
vector<int> edges[N];
int a[N], h[N], c[N];
int used[N], is[N];
ll dp[N][N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> p(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>h[i]>>c[i];
		a[i]--; p[i] = i;
	} sort(p.begin(), p.end(), [&](int i, int j) { return (h[i] < h[j]); });
	for(int i=0, last=0;i<n;){
		int j = i;
		while(j<n && h[p[i]] == h[p[j]]) j++;
		while(i < j) h[p[i]] = last, i++;
		last++;
	}
 	
	vector<vector<int>> cc;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		vector<int> ss;
		int u = i;
		while(!used[u]){
			used[u] = 1;
			ss.push_back(u);
			u = a[u];
		}
		
		vector<int> tmp = {u};
		while(!ss.empty() && ss.back() != u){
			tmp.push_back(ss.back());
			ss.pop_back();
		}
		
		if(ss.empty()) continue;
		for(auto x : tmp) is[x] = 1;
		cc.push_back(tmp);
	}
	
	//~ for(int i=0;i<n;i++) cout<<is[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<n;i++){
		if(is[i] && is[a[i]]) continue;
		edges[a[i]].push_back(i);
	}
	//~ for(int i=0;i<n;i++){
		//~ cout<<i<<" : ";
		//~ for(auto x : edges[i]) cout<<x<<" ";
		//~ cout<<"\n";
	//~ }
	
	function<void(int)> dfs = [&](int u){
		dp[u][h[u]] += c[u];
		for(auto x : edges[u]){
			dfs(x);
			for(int j=0;j<n;j++){
				dp[u][j] += dp[x][j];
			}
		}
		
		for(int j=n-1;~j;j--){
			dp[u][j] = max(dp[u][j], dp[u][j+1]);
		}
	};
	//~ for(int i=0;i<n;i++) cout<<h[i]<<" ";
	//~ cout<<"\n";
	for(int i=0;i<n;i++){
		if(!is[i]) continue;
		dfs(i);
	}
	
	//~ for(int i=0;i<n;i++){
		//~ for(int j=0;j<n;j++) cout<<dp[i][j]<<" ";
		//~ cout<<"\n";
	//~ }
	
	ll res = accumulate(c, c+n, 0ll);
	//~ cout<<res<<"\n";
	for(auto v : cc){
		ll tot = 0;
		for(int j=0;j<n;j++){
			ll rr = 0;
			for(auto x : v){
				rr += dp[x][j];
			} tot = max(tot, rr);
		} res -= tot;
	}
	
	cout<<res<<"\n";
}

/*

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

*/

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