Submission #1146809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146809		Matjaz	Teams (CEOI11_tea)	C++17	70 / 100	2596 ms	23860 KiB

tea

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;


int main(){

	int N;
	cin >> N;
    vector<pair<int,int> > a(N);

    for (int i=0;i<N;i++) {
    	cin >> a[i].first;
    	a[i].second = i + 1;
    }

    sort(a.begin(), a.end());

	vector<int> teams(N, 0);
	vector<int> minmaxteam(N, N);
	vector<int> next(N, -1);

	vector<int> cumulmax_teams(N, 0);

	for (int i=0;i<N;i++){
		if (a[i].first > i + 1) teams[i] = 0; else {
			if (i - a[i].first < 0) teams[i] = 1; else teams[i] = 1 + cumulmax_teams[i - a[i].first];
		}
		if (i == 0) cumulmax_teams[i] = teams[i]; else cumulmax_teams[i] = max(teams[i],cumulmax_teams[i - 1]);
	}


    for (int i=0;i<N;i++){
    	minmaxteam[i] = i + 1; 
    	for (int j=0;j<=i-a[i].first;j++) if (teams[j] > 0 && teams[j] + 1 == teams[i]){
    		if (minmaxteam[i] > max(i-j, minmaxteam[j])){
    			minmaxteam[i] = min(minmaxteam[i], max(i-j, minmaxteam[j]));
    			next[i] = j;
    		}
    	}
    }

    cout << teams[N - 1] << endl;
    int cur = N - 1;
    while (cur > -1){
    	cout << cur - next[cur];
    	for (int i=next[cur]+1; i<=cur;i++) cout << " " << a[i].second;
    	cout << endl;
        cur = next[cur];
    }

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10