Submission #332804

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332804	2020-12-03T12:18:45 Z	AmineWeslati	Bali Sculptures (APIO15_sculpture)	C++14	37 / 100	158 ms	163952 KB

sculpture

//Never stop trying
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")*/
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

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

const int MOD = 1e9 + 7; //998244353
const ll INF = 1e9;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}

#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int N,A,B; 
vi a(MX);
int memo[101][101][2000];

int solve(int i, int n, int m){
	if(i==N){
		if(n>=A && n<=B) return m;
		return INF;
	}

	int &ind=memo[i][n][m];
	if(ind!=-1) return ind;
	int ans=INF;

	int cur=0;
	FOR(j,i,N){
		cur+=a[j];
		ckmin(ans,solve(j+1,n+1,((cur)|(m))));
	}

	return ind=ans;
}

int main() {
    boost; IO();
    memset(memo,-1,sizeof(memo));

    cin>>N>>A>>B;
    FOR(i,0,N) cin>>a[i];
    cout << solve(0,0,0) << endl;
    

    return 0;
}

/* Careful!!!
    .Array bounds
    .Infinite loops
    .Uninitialized variables / empty containers
    .Multisets are shit

   Some insights:
    .Binary search
    .Graph representation
    .Write brute force code
    .Change your approach
*/

Subtask #1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	81004 KB	Output is correct
2	Correct	46 ms	81004 KB	Output is correct
3	Correct	45 ms	81004 KB	Output is correct
4	Correct	45 ms	81004 KB	Output is correct
5	Correct	45 ms	81004 KB	Output is correct
6	Correct	45 ms	81004 KB	Output is correct
7	Correct	45 ms	81004 KB	Output is correct
8	Correct	45 ms	81004 KB	Output is correct
9	Correct	45 ms	81004 KB	Output is correct
10	Correct	44 ms	81004 KB	Output is correct
11	Correct	44 ms	81004 KB	Output is correct
12	Correct	45 ms	81004 KB	Output is correct
13	Correct	47 ms	80908 KB	Output is correct
14	Correct	46 ms	81004 KB	Output is correct
15	Correct	45 ms	81004 KB	Output is correct
16	Correct	52 ms	81004 KB	Output is correct
17	Correct	46 ms	81004 KB	Output is correct
18	Correct	45 ms	81004 KB	Output is correct
19	Correct	47 ms	81004 KB	Output is correct
20	Correct	48 ms	81004 KB	Output is correct
21	Correct	45 ms	81004 KB	Output is correct
22	Correct	44 ms	81004 KB	Output is correct
23	Correct	45 ms	81004 KB	Output is correct
24	Correct	45 ms	81004 KB	Output is correct
25	Correct	44 ms	81004 KB	Output is correct
26	Correct	45 ms	81004 KB	Output is correct
27	Runtime error	158 ms	163952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	81004 KB	Output is correct
2	Correct	49 ms	81004 KB	Output is correct
3	Correct	45 ms	81004 KB	Output is correct
4	Correct	46 ms	81004 KB	Output is correct
5	Correct	46 ms	81004 KB	Output is correct
6	Correct	45 ms	80992 KB	Output is correct
7	Correct	44 ms	80960 KB	Output is correct
8	Correct	46 ms	81004 KB	Output is correct
9	Correct	44 ms	80952 KB	Output is correct
10	Correct	46 ms	81004 KB	Output is correct
11	Correct	44 ms	81004 KB	Output is correct
12	Correct	46 ms	81004 KB	Output is correct
13	Correct	45 ms	81004 KB	Output is correct
14	Correct	45 ms	81004 KB	Output is correct
15	Correct	51 ms	81132 KB	Output is correct
16	Correct	45 ms	81004 KB	Output is correct
17	Correct	45 ms	81004 KB	Output is correct
18	Correct	46 ms	81148 KB	Output is correct
19	Correct	46 ms	81004 KB	Output is correct
20	Correct	46 ms	81004 KB	Output is correct
21	Correct	45 ms	80908 KB	Output is correct
22	Correct	47 ms	81004 KB	Output is correct
23	Correct	49 ms	81004 KB	Output is correct
24	Correct	46 ms	81004 KB	Output is correct
25	Correct	48 ms	81132 KB	Output is correct
26	Correct	47 ms	81004 KB	Output is correct
27	Correct	45 ms	81004 KB	Output is correct
28	Correct	45 ms	81004 KB	Output is correct
29	Correct	47 ms	81004 KB	Output is correct
30	Correct	47 ms	81004 KB	Output is correct
31	Correct	51 ms	81004 KB	Output is correct
32	Correct	51 ms	81004 KB	Output is correct
33	Correct	47 ms	81004 KB	Output is correct
34	Correct	48 ms	81004 KB	Output is correct
35	Correct	47 ms	81004 KB	Output is correct
36	Correct	50 ms	81004 KB	Output is correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	81004 KB	Output is correct
2	Correct	45 ms	81020 KB	Output is correct
3	Correct	46 ms	81004 KB	Output is correct
4	Correct	46 ms	81004 KB	Output is correct
5	Correct	45 ms	81004 KB	Output is correct
6	Correct	45 ms	81004 KB	Output is correct
7	Correct	48 ms	81004 KB	Output is correct
8	Correct	46 ms	81004 KB	Output is correct
9	Correct	45 ms	81004 KB	Output is correct
10	Correct	45 ms	81004 KB	Output is correct
11	Correct	45 ms	81004 KB	Output is correct
12	Correct	45 ms	81004 KB	Output is correct
13	Correct	44 ms	81004 KB	Output is correct
14	Correct	44 ms	81004 KB	Output is correct
15	Correct	46 ms	81004 KB	Output is correct
16	Correct	47 ms	81004 KB	Output is correct
17	Correct	44 ms	81004 KB	Output is correct
18	Correct	49 ms	81132 KB	Output is correct
19	Correct	46 ms	81004 KB	Output is correct
20	Correct	48 ms	81004 KB	Output is correct
21	Correct	47 ms	81004 KB	Output is correct
22	Correct	48 ms	81004 KB	Output is correct
23	Correct	49 ms	81004 KB	Output is correct
24	Correct	48 ms	81004 KB	Output is correct
25	Correct	55 ms	81004 KB	Output is correct
26	Correct	69 ms	81004 KB	Output is correct
27	Correct	85 ms	81004 KB	Output is correct
28	Correct	108 ms	81004 KB	Output is correct
29	Correct	88 ms	81004 KB	Output is correct
30	Correct	84 ms	81004 KB	Output is correct
31	Correct	118 ms	81004 KB	Output is correct
32	Correct	126 ms	81004 KB	Output is correct

Subtask #4
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	81004 KB	Output is correct
2	Correct	51 ms	81004 KB	Output is correct
3	Correct	44 ms	81004 KB	Output is correct
4	Correct	45 ms	81004 KB	Output is correct
5	Correct	45 ms	81004 KB	Output is correct
6	Correct	47 ms	81004 KB	Output is correct
7	Correct	44 ms	81004 KB	Output is correct
8	Correct	46 ms	81004 KB	Output is correct
9	Correct	45 ms	81004 KB	Output is correct
10	Correct	44 ms	81004 KB	Output is correct
11	Correct	44 ms	81004 KB	Output is correct
12	Correct	44 ms	81004 KB	Output is correct
13	Correct	47 ms	81004 KB	Output is correct
14	Correct	44 ms	81004 KB	Output is correct
15	Correct	44 ms	81004 KB	Output is correct
16	Correct	46 ms	81004 KB	Output is correct
17	Correct	46 ms	81004 KB	Output is correct
18	Correct	45 ms	81004 KB	Output is correct
19	Correct	46 ms	81004 KB	Output is correct
20	Correct	45 ms	81004 KB	Output is correct
21	Correct	44 ms	81004 KB	Output is correct
22	Correct	44 ms	81004 KB	Output is correct
23	Correct	44 ms	81004 KB	Output is correct
24	Correct	45 ms	81004 KB	Output is correct
25	Correct	49 ms	81004 KB	Output is correct
26	Correct	48 ms	81132 KB	Output is correct
27	Runtime error	155 ms	163820 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	81004 KB	Output is correct
2	Correct	45 ms	81004 KB	Output is correct
3	Correct	44 ms	81004 KB	Output is correct
4	Correct	44 ms	81004 KB	Output is correct
5	Correct	46 ms	81004 KB	Output is correct
6	Correct	45 ms	81004 KB	Output is correct
7	Correct	47 ms	81004 KB	Output is correct
8	Correct	47 ms	81004 KB	Output is correct
9	Correct	45 ms	81004 KB	Output is correct
10	Correct	46 ms	81004 KB	Output is correct
11	Correct	45 ms	81004 KB	Output is correct
12	Correct	44 ms	81004 KB	Output is correct
13	Correct	44 ms	81004 KB	Output is correct
14	Runtime error	155 ms	163948 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

Submission #332804

Compilation message

Subtask #1 0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 21.0 / 21.0

Subtask #4 0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
21.0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0