oj.uz

Submission #533627

# Submission time Handle Problem Language Result Execution time Memory
533627 2022-03-06T16:56:42 Z CaroLinda Teams (CEOI11_tea) C++14
50 / 100
 2500 ms 26628 KB 
#include <bits/stdc++.h>

#define mk make_pair
#define lp(i,a,b) for(int i = a ; i < b; i++ )
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std ;

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

	int N ;
	cin >> N ;
	vector<int> arr(N) , idx(N) ; iota(all(idx) , 0) ;
	vector<int> corte(N) ;
	for(auto &e : arr ) cin >> e ;
	sort(all(idx),[&](int a, int b) { return arr[a] < arr[b] ; }) ;
	vector<pair<int,int> > dp(N) ;
	for(int i = 0 ; i < N ; i++){
		if( i+1 < arr[idx[i]] ){
			dp[i] = make_pair( -1 , -N-1 ) ;
			continue ;
		}
		dp[i] = make_pair(1 , -i-1 ) ;
		corte[i] = -1 ;
		for(int j = i-arr[idx[i]] ; j >= 0 ; j-- ){
			pair<int,int> aux = mk(dp[j].first+1 , min(dp[j].second,-(i-j)) ) ;
			if(aux > dp[i]){
				dp[i] = aux ;
				corte[i] = j ;
			}
		}
	}

	vector< vector<int> > ans ;

	int x = N-1 ;
	while(x != -1){

		ans.push_back(vector<int>()) ;
		for(int i = corte[x]+1 ; i <= x ; i++ ) ans.back().push_back(idx[i]) ;
		x = corte[x] ;

	}

	cout << sz(ans) << "\n" ;
	for(auto e : ans ){
		cout << sz(e) << " " ;
		for(auto ee : e ) cout << ee+1 << " " ;
			cout << "\n" ;
	}

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 460 KB Output is correct
2 Correct 15 ms 432 KB Output is correct
3 Correct 15 ms 428 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 484 KB Output is correct
2 Correct 11 ms 432 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2312 ms 3252 KB Output is correct
2 Execution timed out 2580 ms 2124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2568 ms 2496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2598 ms 18584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2506 ms 25668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2505 ms 26628 KB Time limit exceeded
2 Halted 0 ms 0 KB -