Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <cstring>
- using namespace std;
- struct stanje {
- int x, a, b, c;
- void normalize() {
- if( a > b ) swap( a, b );
- if( a > c ) swap( a, c );
- if( b > c ) swap( b, c );
- }
- stanje() {};
- stanje( int _x, int _a, int _b, int _c ) { x = _x; a = _a; b = _b; c = _c; normalize(); }
- friend bool operator < ( const stanje &a, const stanje &b ) {
- if( a.x != b.x ) return a.x < b.x;
- if( a.a != b.a ) return a.a < b.a;
- if( a.b != b.b ) return a.b < b.b;
- return a.c < b.c;
- }
- };
- int bio[62][600][600][10];
- int a[105], s[105];
- int ans, n;
- inline int get( int x, int a, int b, int c ) {
- if( (bio[x][a][b][c>>5]>>(c&31))&1 ) return 1;
- bio[x][a][b][c>>5] |= 1<<(c&31);
- return 0;
- }
- void dfs( stanje x ) {
- if(x.a >600 || x.b>600 || x.c>600 ) return;
- if( x.a == x.b && x.b == x.c && x.a > ans ) ans = x.a;
- int w = x.a + x.b + x.c + s[x.x]; w /= 3;
- if( w < ans || x.a > w || x.b > w || x.c > w ) return;
- if( x.x == n ) return;
- if( get( x.x, x.a, x.b, x.c ) ) return;
- dfs( stanje( x.x+1, x.a, x.b, x.c ) );
- dfs( stanje( x.x+1, x.a+a[x.x], x.b, x.c ) );
- dfs( stanje( x.x+1, x.a, x.b+a[x.x], x.c ) );
- dfs( stanje( x.x+1, x.a, x.b, x.c+a[x.x] ) );
- }
- int main( void ) {
- while( scanf( "%d", &n ) == 1 ) {
- if( n == 0 ) break;
- int ss = 0;
- for( int i = 0; i < n; ++i ) {
- scanf( "%d", a+i );
- ss += a[i];
- }
- // printf( "%d\n", ss/3 );
- s[n] = 0;
- for( int i = n-1; i >= 0; --i )
- s[i] = s[i+1] + a[i];
- ans = 0;
- memset( bio, 0, sizeof( bio ) );
- dfs( stanje( 0, 0, 0, 0 ) );
- printf( "%d\n", ans );
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement