oj.uz

Submission #518952

# Submission time Handle Problem Language Result Execution time Memory
518952 2022-01-25T09:14:55 Z hivakarami Worst Reporter 4 (JOI21_worst_reporter4) C++14
14 / 100
 517 ms 400244 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 311 ms 399800 KB Output is correct
6 Correct 285 ms 399832 KB Output is correct
7 Correct 271 ms 399912 KB Output is correct
8 Correct 289 ms 399996 KB Output is correct
9 Correct 278 ms 400000 KB Output is correct
10 Correct 276 ms 399920 KB Output is correct
11 Correct 294 ms 399948 KB Output is correct
12 Correct 278 ms 400060 KB Output is correct
13 Correct 279 ms 400008 KB Output is correct
14 Correct 274 ms 400068 KB Output is correct
15 Correct 270 ms 400020 KB Output is correct
16 Correct 276 ms 399976 KB Output is correct
17 Correct 269 ms 399984 KB Output is correct
18 Correct 270 ms 399896 KB Output is correct
19 Correct 272 ms 400020 KB Output is correct
20 Correct 270 ms 400020 KB Output is correct
21 Correct 289 ms 400132 KB Output is correct
22 Correct 504 ms 400004 KB Output is correct
23 Correct 517 ms 400016 KB Output is correct
24 Correct 404 ms 400052 KB Output is correct
25 Correct 421 ms 399948 KB Output is correct
26 Correct 263 ms 400004 KB Output is correct
27 Correct 278 ms 399932 KB Output is correct
28 Correct 272 ms 399984 KB Output is correct
29 Correct 276 ms 400244 KB Output is correct
30 Correct 266 ms 399808 KB Output is correct
31 Correct 264 ms 400036 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 311 ms 399800 KB Output is correct
6 Correct 285 ms 399832 KB Output is correct
7 Correct 271 ms 399912 KB Output is correct
8 Correct 289 ms 399996 KB Output is correct
9 Correct 278 ms 400000 KB Output is correct
10 Correct 276 ms 399920 KB Output is correct
11 Correct 294 ms 399948 KB Output is correct
12 Correct 278 ms 400060 KB Output is correct
13 Correct 279 ms 400008 KB Output is correct
14 Correct 274 ms 400068 KB Output is correct
15 Correct 270 ms 400020 KB Output is correct
16 Correct 276 ms 399976 KB Output is correct
17 Correct 269 ms 399984 KB Output is correct
18 Correct 270 ms 399896 KB Output is correct
19 Correct 272 ms 400020 KB Output is correct
20 Correct 270 ms 400020 KB Output is correct
21 Correct 289 ms 400132 KB Output is correct
22 Correct 504 ms 400004 KB Output is correct
23 Correct 517 ms 400016 KB Output is correct
24 Correct 404 ms 400052 KB Output is correct
25 Correct 421 ms 399948 KB Output is correct
26 Correct 263 ms 400004 KB Output is correct
27 Correct 278 ms 399932 KB Output is correct
28 Correct 272 ms 399984 KB Output is correct
29 Correct 276 ms 400244 KB Output is correct
30 Correct 266 ms 399808 KB Output is correct
31 Correct 264 ms 400036 KB Output is correct
32 Correct 287 ms 400164 KB Output is correct
33 Runtime error 9 ms 1600 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 311 ms 399800 KB Output is correct
6 Correct 285 ms 399832 KB Output is correct
7 Correct 271 ms 399912 KB Output is correct
8 Correct 289 ms 399996 KB Output is correct
9 Correct 278 ms 400000 KB Output is correct
10 Correct 276 ms 399920 KB Output is correct
11 Correct 294 ms 399948 KB Output is correct
12 Correct 278 ms 400060 KB Output is correct
13 Correct 279 ms 400008 KB Output is correct
14 Correct 274 ms 400068 KB Output is correct
15 Correct 270 ms 400020 KB Output is correct
16 Correct 276 ms 399976 KB Output is correct
17 Correct 269 ms 399984 KB Output is correct
18 Correct 270 ms 399896 KB Output is correct
19 Correct 272 ms 400020 KB Output is correct
20 Correct 270 ms 400020 KB Output is correct
21 Correct 289 ms 400132 KB Output is correct
22 Correct 504 ms 400004 KB Output is correct
23 Correct 517 ms 400016 KB Output is correct
24 Correct 404 ms 400052 KB Output is correct
25 Correct 421 ms 399948 KB Output is correct
26 Correct 263 ms 400004 KB Output is correct
27 Correct 278 ms 399932 KB Output is correct
28 Correct 272 ms 399984 KB Output is correct
29 Correct 276 ms 400244 KB Output is correct
30 Correct 266 ms 399808 KB Output is correct
31 Correct 264 ms 400036 KB Output is correct
32 Correct 287 ms 400164 KB Output is correct
33 Runtime error 9 ms 1600 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -