1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cout.tie(0); cout.tie(0);
	int k, D, N;
	cin >> D >> k;
	N=k;
	vector<vector<int>> tablica;
	vector<int> vec, dp;
	for(int i=1; i<=k; i++) {
		vec.push_back(0);
		dp.push_back(0);
	}	
	int n, a;
	tablica.push_back(vec);
	for(int i=2; i<=D; i++) {
		vec.clear();
		cin >> n;
		for(int j=1; j<=n; j++) {
			cin >> a;
			vec.push_back(a);
			dp.push_back(0);
		}
		tablica.push_back(vec);	
		N+=n;
	}
	int obecny=N-1, pelne=N-1, poprzednik;	
	//cout << "przeszlo,   dp.size() = " << dp.size() << endl;
	for(int i=D-1; i>=0; i--) {
		pelne-=tablica[i].size();
		//cout << "DOSZLO DO: " << i << endl;
		for(int j=tablica[i].size()-1; j>=0; j--) {
			//cout << j << endl;
			if(tablica[i][j]==0 && dp[obecny]==0) {
				dp[obecny]=1;
			}	
			else if(tablica[i][j]!=0) {
				if(dp[obecny] == 0) {
					dp[obecny]=1;
				}	
				poprzednik = pelne - tablica[i-1].size() + tablica[i][j];
				//cout << "POPRZEDNIK = " << poprzednik << endl;
				dp[poprzednik]+=dp[obecny];
			}	
			obecny--;
		}	
	}	
	int ilewolnych=0;
	int wynik=0;
	int ilepoprzednich=0;
	obecny=0;
	unordered_set<int> S;
	for(int i=0; i<D; i++) {
		S.clear();
		for(int j=0; j<tablica[i].size(); j++) {
			if(tablica[i][j]!=0) {
				S.insert(tablica[i][j]);
			}	
		}
		ilewolnych += ilepoprzednich - S.size();
		for(int j=0; j<tablica[i].size(); j++) {
			if(tablica[i][j]==0) {
				ilewolnych-=dp[obecny];
			}	
			obecny++;
		}	
		if(ilewolnych<0) {
			wynik-=ilewolnych;
			ilewolnych=0;
		}		
		ilepoprzednich = tablica[i].size();
	}	
	cout << wynik;
}