Submission #518952

#	Time	Username	Problem	Language	Result	Execution time	Memory
518952		hivakarami	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	14 / 100	517 ms	400244 KiB

worst_reporter2

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

typedef long long int ll;
typedef long double ld;
 
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define SZ(v) int(v.size())
#define all(v) (v).begin(),(v).end()
 
const int N = 5000 + 100;
const ll inf = 1e17;
const ll base = 313;
const ll mod = 1009;
 
ll p[N], a[N], c[N], ps[N], dp[N][N], dp2[N][N];
vector<ll> v, adj[N]; 


int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	

	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> p[i] >> a[i] >> c[i];
		v.pb(a[i]);
		p[i]--;
		adj[p[i]].pb(i);
	}
	v.pb(1);
	sort(all(v));
	
	for(int i = n-1; i >= 0; i--)
	{
		for(int j = 0; j < v.size(); j++)
		{
			dp[i][j] = c[i];
			if(v[j] == a[i])
				dp[i][j] = 0;
			
			for(auto x : adj[i])
			{
				dp[i][j] += dp2[x][j];
				//cout <<"///" << ' ' << j << v[j] << ' ' << x << ' ' << dp2[x][j] << endl;
			}
			//cout << i << ' ' << j << ' ' << v[j] << ' ' << dp[i][j] << endl;	
		}
		//cout << endl;
		dp2[i][SZ(v)] = inf;
		for(int j = SZ(v)-1; j >= 0; j--)
			dp2[i][j] = min(dp2[i][j+1], dp[i][j]);
	}
	
	
	cout << dp2[0][0] << endl;
	
	
	
	return 0;
}
 
 
 
 
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 2 4

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

*/
 
 

 
 

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int j = 0; j < v.size(); j++)
      |                  ~~^~~~~~~~~~

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