Submission #991684

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991684	2024-06-02T19:20:45 Z	_rain_	Bali Sculptures (APIO15_sculpture)	C++14	9 / 100	68 ms	604 KB

sculpture

/** author : Knquin_ **/
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;

#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define sz(x) (x).size()
#define all(x) (x).begin() , (x).end()

#define FOR(i ,a , b) for (int i = (a); i <= (b); ++i)
#define FORD(i , a , b) for (int i = (b); i >= (a); --i)
#define REP(i , a , b) for (int i = (a); i < (b); ++i)
#define REPD(i , a , b) for (int i = (b) - 1 ; i >= (a); --i)

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
template<class T>
    bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
    bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
    T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
    T lcm(T x , T y) {return (x * y) / gcd(x , y);}

template <class T> 
    void compress(vector<T> &a)
    {
        sort(a.begin() , a.end());
        a.resize(unique(a.begin() , a.end()) - a.begin());
        return;
    }
template<class T>
    void printArr(T& container , string separator = "" , string finish = "\n")
    {
        for (auto& item : container) cout << item << separator;
        cout << finish;
    }

const int maxn = 20;
int n , A , B;
i64 a[maxn + 2];

int32_t main()
{
    iostream::sync_with_stdio(false); cin.tie(0);
    const string name = "main";
    if (fopen((name + ".inp").c_str() , "r"))
    {
        (void)!freopen((name + ".inp").c_str() , "r" , stdin);
        (void)!freopen((name + ".ans").c_str() , "w+", stdout);
    }
    cin >> n >> A >> B;
    if (n > 20) return 0;
    REP(i , 0 , n) cin >> a[i];
    i64 answer = (i64)1e18;
    vector<int> bucket;
    FOR(mask , 0 , MASK(n) - 1)
    {
    	if (__builtin_popcount(mask) == 0) continue;
    	int used = 0 , last = -1 ;
    	i64 cur = 0 , sum = 0;
    	REP(i , 0 , n)
    	{
    		if (BIT(mask ,i) != last)
    		{
    			++used;
    			sum |= cur;
    			cur = a[i];
    			last = BIT(mask , i);
    		}
    		else cur += a[i];
    	}
    	sum |= cur;
    	if (A <= used && used <= B) 
    		{
    			if (minimize(answer , sum))
    			{
    				bucket.clear();
    				REP(i , 0 , n) bucket.push_back(BIT(mask , i));
    			}
    		}
    }
    cout << answer << '\n';
}

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	7 ms	348 KB	Output is correct
8	Correct	62 ms	432 KB	Output is correct
9	Correct	62 ms	348 KB	Output is correct
10	Correct	64 ms	348 KB	Output is correct
11	Correct	62 ms	348 KB	Output is correct
12	Correct	64 ms	348 KB	Output is correct
13	Correct	62 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	456 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	2 ms	348 KB	Output is correct
20	Correct	8 ms	460 KB	Output is correct
21	Correct	66 ms	448 KB	Output is correct
22	Correct	59 ms	348 KB	Output is correct
23	Correct	59 ms	348 KB	Output is correct
24	Correct	62 ms	348 KB	Output is correct
25	Correct	60 ms	348 KB	Output is correct
26	Correct	60 ms	348 KB	Output is correct
27	Correct	0 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	31 ms	348 KB	Output is correct
31	Correct	60 ms	348 KB	Output is correct
32	Correct	62 ms	344 KB	Output is correct
33	Correct	60 ms	348 KB	Output is correct
34	Correct	62 ms	592 KB	Output is correct
35	Correct	62 ms	348 KB	Output is correct
36	Correct	60 ms	348 KB	Output is correct

Subtask #2

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	7 ms	348 KB	Output is correct
8	Correct	62 ms	348 KB	Output is correct
9	Correct	62 ms	348 KB	Output is correct
10	Correct	62 ms	348 KB	Output is correct
11	Correct	62 ms	348 KB	Output is correct
12	Correct	62 ms	440 KB	Output is correct
13	Correct	62 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	2 ms	348 KB	Output is correct
20	Correct	8 ms	348 KB	Output is correct
21	Correct	59 ms	348 KB	Output is correct
22	Correct	60 ms	348 KB	Output is correct
23	Correct	60 ms	348 KB	Output is correct
24	Correct	62 ms	436 KB	Output is correct
25	Correct	60 ms	348 KB	Output is correct
26	Correct	60 ms	348 KB	Output is correct
27	Incorrect	0 ms	348 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	7 ms	348 KB	Output is correct
8	Correct	62 ms	436 KB	Output is correct
9	Correct	62 ms	348 KB	Output is correct
10	Correct	63 ms	348 KB	Output is correct
11	Correct	62 ms	348 KB	Output is correct
12	Correct	62 ms	348 KB	Output is correct
13	Correct	62 ms	432 KB	Output is correct
14	Incorrect	0 ms	348 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	7 ms	348 KB	Output is correct
8	Correct	62 ms	348 KB	Output is correct
9	Correct	62 ms	348 KB	Output is correct
10	Correct	63 ms	344 KB	Output is correct
11	Correct	62 ms	348 KB	Output is correct
12	Correct	64 ms	596 KB	Output is correct
13	Correct	62 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	2 ms	460 KB	Output is correct
20	Correct	7 ms	464 KB	Output is correct
21	Correct	60 ms	348 KB	Output is correct
22	Correct	59 ms	348 KB	Output is correct
23	Correct	59 ms	348 KB	Output is correct
24	Correct	62 ms	348 KB	Output is correct
25	Correct	60 ms	348 KB	Output is correct
26	Correct	62 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	31 ms	460 KB	Output is correct
31	Correct	60 ms	348 KB	Output is correct
32	Correct	62 ms	348 KB	Output is correct
33	Correct	60 ms	348 KB	Output is correct
34	Correct	61 ms	440 KB	Output is correct
35	Correct	65 ms	440 KB	Output is correct
36	Correct	60 ms	348 KB	Output is correct
37	Incorrect	0 ms	348 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #5

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	348 KB	Output is correct
7	Correct	7 ms	464 KB	Output is correct
8	Correct	62 ms	432 KB	Output is correct
9	Correct	62 ms	436 KB	Output is correct
10	Correct	61 ms	348 KB	Output is correct
11	Correct	62 ms	348 KB	Output is correct
12	Correct	62 ms	348 KB	Output is correct
13	Correct	62 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	31 ms	348 KB	Output is correct
18	Correct	60 ms	436 KB	Output is correct
19	Correct	62 ms	348 KB	Output is correct
20	Correct	60 ms	348 KB	Output is correct
21	Correct	64 ms	348 KB	Output is correct
22	Correct	68 ms	440 KB	Output is correct
23	Correct	61 ms	348 KB	Output is correct
24	Incorrect	1 ms	348 KB	Output isn't correct
25	Halted	0 ms	0 KB	-