Submission #332799

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332799	2020-12-03T12:13:56 Z	AmineWeslati	Bali Sculptures (APIO15_sculpture)	C++14	0 / 100	38 ms	36076 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;
#define int 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 = 1e18;
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][200];

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;
}

int32_t 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	11 ms	17900 KB	Output is correct
2	Correct	10 ms	17900 KB	Output is correct
3	Correct	10 ms	17900 KB	Output is correct
4	Correct	10 ms	17900 KB	Output is correct
5	Correct	10 ms	17900 KB	Output is correct
6	Correct	10 ms	17900 KB	Output is correct
7	Correct	10 ms	17900 KB	Output is correct
8	Correct	10 ms	17900 KB	Output is correct
9	Correct	11 ms	17900 KB	Output is correct
10	Correct	10 ms	17900 KB	Output is correct
11	Correct	10 ms	17900 KB	Output is correct
12	Correct	10 ms	17900 KB	Output is correct
13	Correct	11 ms	17900 KB	Output is correct
14	Correct	10 ms	17900 KB	Output is correct
15	Correct	11 ms	17916 KB	Output is correct
16	Correct	10 ms	17900 KB	Output is correct
17	Correct	10 ms	17900 KB	Output is correct
18	Correct	10 ms	17900 KB	Output is correct
19	Correct	10 ms	17900 KB	Output is correct
20	Correct	11 ms	17900 KB	Output is correct
21	Correct	11 ms	17900 KB	Output is correct
22	Correct	10 ms	17900 KB	Output is correct
23	Correct	10 ms	17900 KB	Output is correct
24	Correct	10 ms	17900 KB	Output is correct
25	Correct	12 ms	18028 KB	Output is correct
26	Correct	11 ms	17900 KB	Output is correct
27	Runtime error	38 ms	35948 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #2
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	17920 KB	Output is correct
2	Correct	10 ms	17900 KB	Output is correct
3	Correct	11 ms	17900 KB	Output is correct
4	Correct	11 ms	17900 KB	Output is correct
5	Correct	10 ms	17900 KB	Output is correct
6	Correct	11 ms	17900 KB	Output is correct
7	Correct	10 ms	17900 KB	Output is correct
8	Correct	10 ms	17900 KB	Output is correct
9	Correct	10 ms	17900 KB	Output is correct
10	Correct	10 ms	17900 KB	Output is correct
11	Correct	10 ms	17900 KB	Output is correct
12	Correct	10 ms	17900 KB	Output is correct
13	Correct	11 ms	17900 KB	Output is correct
14	Correct	10 ms	17900 KB	Output is correct
15	Correct	11 ms	17900 KB	Output is correct
16	Correct	10 ms	17900 KB	Output is correct
17	Correct	11 ms	17900 KB	Output is correct
18	Correct	10 ms	17900 KB	Output is correct
19	Correct	10 ms	17900 KB	Output is correct
20	Correct	10 ms	17900 KB	Output is correct
21	Correct	11 ms	17900 KB	Output is correct
22	Correct	10 ms	17900 KB	Output is correct
23	Correct	10 ms	17900 KB	Output is correct
24	Correct	10 ms	17900 KB	Output is correct
25	Correct	11 ms	17900 KB	Output is correct
26	Correct	11 ms	17900 KB	Output is correct
27	Correct	11 ms	17900 KB	Output is correct
28	Correct	11 ms	17920 KB	Output is correct
29	Correct	11 ms	17900 KB	Output is correct
30	Correct	12 ms	17900 KB	Output is correct
31	Correct	14 ms	17900 KB	Output is correct
32	Correct	12 ms	17900 KB	Output is correct
33	Correct	13 ms	17900 KB	Output is correct
34	Correct	13 ms	17900 KB	Output is correct
35	Incorrect	13 ms	17900 KB	Output isn't correct
36	Halted	0 ms	0 KB	-

Subtask #3
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	17900 KB	Output is correct
2	Correct	10 ms	17900 KB	Output is correct
3	Correct	10 ms	17900 KB	Output is correct
4	Correct	10 ms	17900 KB	Output is correct
5	Correct	12 ms	17900 KB	Output is correct
6	Correct	10 ms	17900 KB	Output is correct
7	Correct	10 ms	17900 KB	Output is correct
8	Correct	10 ms	17900 KB	Output is correct
9	Correct	10 ms	17900 KB	Output is correct
10	Correct	10 ms	17900 KB	Output is correct
11	Correct	10 ms	17900 KB	Output is correct
12	Correct	10 ms	17900 KB	Output is correct
13	Correct	13 ms	17900 KB	Output is correct
14	Correct	10 ms	17900 KB	Output is correct
15	Correct	10 ms	17900 KB	Output is correct
16	Correct	11 ms	17900 KB	Output is correct
17	Correct	13 ms	17900 KB	Output is correct
18	Correct	14 ms	17900 KB	Output is correct
19	Correct	12 ms	17900 KB	Output is correct
20	Correct	12 ms	17900 KB	Output is correct
21	Correct	13 ms	17900 KB	Output is correct
22	Incorrect	13 ms	17920 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	17900 KB	Output is correct
2	Correct	10 ms	17900 KB	Output is correct
3	Correct	11 ms	17900 KB	Output is correct
4	Correct	10 ms	17900 KB	Output is correct
5	Correct	10 ms	17900 KB	Output is correct
6	Correct	10 ms	17900 KB	Output is correct
7	Correct	10 ms	17900 KB	Output is correct
8	Correct	11 ms	17900 KB	Output is correct
9	Correct	11 ms	17900 KB	Output is correct
10	Correct	11 ms	17900 KB	Output is correct
11	Correct	10 ms	17900 KB	Output is correct
12	Correct	10 ms	17900 KB	Output is correct
13	Correct	10 ms	17900 KB	Output is correct
14	Correct	10 ms	17900 KB	Output is correct
15	Correct	10 ms	17900 KB	Output is correct
16	Correct	10 ms	17900 KB	Output is correct
17	Correct	10 ms	17900 KB	Output is correct
18	Correct	10 ms	17900 KB	Output is correct
19	Correct	10 ms	17900 KB	Output is correct
20	Correct	10 ms	17900 KB	Output is correct
21	Correct	10 ms	17900 KB	Output is correct
22	Correct	10 ms	17900 KB	Output is correct
23	Correct	10 ms	17900 KB	Output is correct
24	Correct	10 ms	17920 KB	Output is correct
25	Correct	10 ms	17900 KB	Output is correct
26	Correct	10 ms	17912 KB	Output is correct
27	Runtime error	34 ms	35948 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	11 ms	17900 KB	Output is correct
2	Correct	10 ms	17900 KB	Output is correct
3	Correct	10 ms	17900 KB	Output is correct
4	Correct	10 ms	17900 KB	Output is correct
5	Correct	12 ms	17900 KB	Output is correct
6	Correct	11 ms	17900 KB	Output is correct
7	Correct	10 ms	17900 KB	Output is correct
8	Correct	10 ms	17900 KB	Output is correct
9	Correct	10 ms	17900 KB	Output is correct
10	Correct	11 ms	17900 KB	Output is correct
11	Correct	10 ms	17900 KB	Output is correct
12	Correct	10 ms	17900 KB	Output is correct
13	Correct	10 ms	17900 KB	Output is correct
14	Runtime error	34 ms	36076 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

Submission #332799

Compilation message

Subtask #1 0 / 9.0

Subtask #2 0 / 16.0

Subtask #3 0 / 21.0

Subtask #4 0 / 25.0

Subtask #5 0 / 29.0

Subtask #1
0 / 9.0

Subtask #2
0 / 16.0

Subtask #3
0 / 21.0

Subtask #4
0 / 25.0

Subtask #5
0 / 29.0