oj.uz

Submission #642389

# Submission time Handle Problem Language Result Execution time Memory
642389 2022-09-19T10:44:12 Z manizare Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 221112 KB 
#include<bits/stdc++.h>
 
#define all(a) a.begin(),a.end()
#define pb push_back
#pragma GCC target ("avx")
#pragma GCC optimaze ("unroll-loops")
using namespace std ;
 
const int maxn = 1e5 + 10 , maxq = 1e3+10 , mod = 998244353 ,inf = 1e9 ;
int a[maxn] , dp[maxq][maxn] , pre[maxn] ;
 
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t ;
	cin >> t ;
	while(t--){
		int n ;
		cin >> n ;
		for(int i =1 ; i<= n ; i++){
			cin >> a[i] ;
			pre[i] = pre[i-1] + a[i] ;
		}
//		for(int i = 0; i <= n ; i++)
//			for(int j = 0 ; j <= (maxn-10) ; j++)
//				dp[i][j] = -1 ;
			
		
		dp[0][0] = 0 ;
		for(int i = 1; i <= n ; i++){
			for(int j = 0 ; j <= (maxn-10) ; j++){
				dp[i][j] = dp[i-1][j] ;
				if(a[i] <= j){
					dp[i][j] = max(dp[i-1][j-a[i]] , dp[i][j]);
				}
				if(j == a[i] && j != 0)dp[i][j] = i ;
				else if(dp[i][j] == 0 && j == 0)dp[i][j] =0 ;
			}
		}	
//		for(int i = 1; i<= n ; i++){
//			for(int j = 0 ; j <= 8 ; j ++){
//				cout << dp[i][j] << " " ;
//			}
//			cout << "\n";
//		}
		vector <int> v; 
		for(int i =1 ;i <= n ; i++){
			int x = 1 , ok = 0;
			for(int j = i ; j <= n ; j++){
				int sum = pre[j] - pre[x-1] ;
				if(sum % 2 == 1 || dp[j][sum/2] < x || dp[j][sum/2] == -1){
					ok = 1; 
					break;
				} 
				x++;
			}
			if(ok == 0)v.pb(i);
		}
		cout << v.size() << " " ;
		for(short i = 0 ; i <v.size();i++)cout << v[i] << " " ;
		cout << "\n";
	}
	return 0 ; 
}

Compilation message

Main.cpp:6: warning: ignoring '#pragma GCC optimaze' [-Wunknown-pragmas]
    6 | #pragma GCC optimaze ("unroll-loops")
      | 
Main.cpp: In function 'int main()':
Main.cpp:59:23: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for(short i = 0 ; i <v.size();i++)cout << v[i] << " " ;
      |                     ~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 12064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 26552 KB Output is correct
2 Correct 491 ms 46252 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 100504 KB Output is correct
2 Correct 1569 ms 150260 KB Output is correct
3 Correct 1560 ms 169836 KB Output is correct
4 Execution timed out 2102 ms 221112 KB Time limit exceeded
5 Halted 0 ms 0 KB -