oj.uz

Submission #707981

# Submission time Handle Problem Language Result Execution time Memory
707981 2023-03-10T16:31:06 Z ssense Bali Sculptures (APIO15_sculpture) C++14
16 / 100
 1000 ms 65332 KB 
#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu

int dp[105][2049][105];

void solve()
{
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    vint y = read(n);
    prefix_sum pref;
    pref.build(y);
    dp[0][0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        //se termina la i grupul
        for(int j = 0; j < i; j++)
        {
            for(int orr = 0; orr <= 2048; orr++)
            {
                for(int grup = 0; grup < b; grup++)
                {
                    dp[i][(orr|pref.get(j+1, i))][grup+1]|=dp[j][orr][grup];
                }
            }
        }
    }
    int ans = MX;
    for(int orr = 2048; orr >= 0; orr--)
    {
        for(int grup = a; grup <= b; grup++)
        {
            ans = min(ans, (dp[n][orr][grup] ? orr : MX));
        }
    }
    cout << ans << endl;
}

int32_t main(){
    startt
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}


/*
6 1 3
8 1 2 1 5 4
 */

Compilation message

sculpture.cpp: In member function 'void prefix_sum::build(std::vector<int>)':
sculpture.cpp:19:667: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | int ceildiv(int one, int two) {if (one % two == 0) {return one / two;}else {return one / two + 1;}} int power(int n, int pow, int m) {if (pow == 0) return 1;if (pow % 2 == 0) {ll x = power(n, pow / 2, m);return (x * x) % m;}else return (power(n, pow - 1, m) * n) % m;} int gcd(int a, int b) { if (!b)return a; return gcd(b, a % b);} int factorial(int n, int mod) {if (n > 1)return (n * factorial(n - 1, mod)) % mod; else return 1;} int lcm(int a, int b) {return (a * b) / gcd(a, b);} vector<int> read(int n) {vector<int> a; for (int i = 0; i < n; i++) { int x; cin >> x; a.pb(x);} return a;}struct prefix_sum{vint pref;void build(vint a){pref.pb(0);for(int i = 0; i < a.size(); i++){pref.pb(pref.back()+a[i]);}}int get(int l, int r){return pref[r]-pref[l-1];}};//mesanu
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 6 ms 6996 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 5 ms 8660 KB Output is correct
6 Correct 31 ms 12884 KB Output is correct
7 Correct 15 ms 14488 KB Output is correct
8 Correct 17 ms 17176 KB Output is correct
9 Correct 19 ms 17120 KB Output is correct
10 Correct 19 ms 16956 KB Output is correct
11 Correct 13 ms 16896 KB Output is correct
12 Correct 18 ms 17100 KB Output is correct
13 Correct 58 ms 17088 KB Output is correct
14 Correct 4 ms 5332 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 5 ms 5332 KB Output is correct
17 Correct 3 ms 4436 KB Output is correct
18 Correct 8 ms 8660 KB Output is correct
19 Correct 32 ms 12928 KB Output is correct
20 Correct 14 ms 14588 KB Output is correct
21 Correct 29 ms 17148 KB Output is correct
22 Correct 31 ms 16972 KB Output is correct
23 Correct 31 ms 16932 KB Output is correct
24 Correct 18 ms 16912 KB Output is correct
25 Correct 33 ms 17096 KB Output is correct
26 Correct 47 ms 17168 KB Output is correct
27 Runtime error 2 ms 340 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 6 ms 7056 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 6 ms 8660 KB Output is correct
6 Correct 32 ms 12908 KB Output is correct
7 Correct 16 ms 14480 KB Output is correct
8 Correct 20 ms 17084 KB Output is correct
9 Correct 22 ms 17108 KB Output is correct
10 Correct 18 ms 16980 KB Output is correct
11 Correct 12 ms 16904 KB Output is correct
12 Correct 17 ms 17108 KB Output is correct
13 Correct 58 ms 17148 KB Output is correct
14 Correct 4 ms 5332 KB Output is correct
15 Correct 5 ms 5332 KB Output is correct
16 Correct 5 ms 5332 KB Output is correct
17 Correct 3 ms 4436 KB Output is correct
18 Correct 8 ms 8752 KB Output is correct
19 Correct 32 ms 12904 KB Output is correct
20 Correct 14 ms 14676 KB Output is correct
21 Correct 29 ms 17100 KB Output is correct
22 Correct 31 ms 16972 KB Output is correct
23 Correct 30 ms 16896 KB Output is correct
24 Correct 15 ms 16980 KB Output is correct
25 Correct 30 ms 17112 KB Output is correct
26 Correct 48 ms 17072 KB Output is correct
27 Correct 71 ms 17908 KB Output is correct
28 Correct 62 ms 21468 KB Output is correct
29 Correct 68 ms 32240 KB Output is correct
30 Correct 217 ms 35660 KB Output is correct
31 Correct 363 ms 42432 KB Output is correct
32 Correct 373 ms 42220 KB Output is correct
33 Correct 48 ms 42188 KB Output is correct
34 Correct 366 ms 42468 KB Output is correct
35 Correct 326 ms 42396 KB Output is correct
36 Correct 229 ms 42444 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 6 ms 6996 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 6 ms 8660 KB Output is correct
6 Correct 32 ms 12912 KB Output is correct
7 Correct 14 ms 14520 KB Output is correct
8 Correct 19 ms 17208 KB Output is correct
9 Correct 18 ms 17100 KB Output is correct
10 Correct 18 ms 16912 KB Output is correct
11 Correct 12 ms 16980 KB Output is correct
12 Correct 18 ms 17164 KB Output is correct
13 Correct 58 ms 17104 KB Output is correct
14 Correct 73 ms 17964 KB Output is correct
15 Correct 61 ms 21292 KB Output is correct
16 Correct 69 ms 32304 KB Output is correct
17 Correct 233 ms 35624 KB Output is correct
18 Correct 386 ms 42400 KB Output is correct
19 Correct 367 ms 42300 KB Output is correct
20 Correct 43 ms 42168 KB Output is correct
21 Correct 367 ms 42440 KB Output is correct
22 Correct 323 ms 42388 KB Output is correct
23 Correct 226 ms 42488 KB Output is correct
24 Correct 354 ms 42676 KB Output is correct
25 Correct 375 ms 54248 KB Output is correct
26 Correct 925 ms 65332 KB Output is correct
27 Execution timed out 1065 ms 45504 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5332 KB Output is correct
2 Correct 6 ms 6996 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 3 ms 4436 KB Output is correct
5 Correct 7 ms 8660 KB Output is correct
6 Correct 32 ms 12968 KB Output is correct
7 Correct 16 ms 14548 KB Output is correct
8 Correct 19 ms 17308 KB Output is correct
9 Correct 19 ms 17236 KB Output is correct
10 Correct 19 ms 16868 KB Output is correct
11 Correct 14 ms 16964 KB Output is correct
12 Correct 19 ms 17112 KB Output is correct
13 Correct 59 ms 17072 KB Output is correct
14 Correct 4 ms 5284 KB Output is correct
15 Correct 5 ms 5332 KB Output is correct
16 Correct 5 ms 5332 KB Output is correct
17 Correct 4 ms 4436 KB Output is correct
18 Correct 9 ms 8700 KB Output is correct
19 Correct 31 ms 12876 KB Output is correct
20 Correct 17 ms 14676 KB Output is correct
21 Correct 33 ms 17152 KB Output is correct
22 Correct 30 ms 16980 KB Output is correct
23 Correct 30 ms 16888 KB Output is correct
24 Correct 15 ms 16936 KB Output is correct
25 Correct 30 ms 17180 KB Output is correct
26 Correct 47 ms 17136 KB Output is correct
27 Runtime error 2 ms 468 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5332 KB Output is correct
2 Correct 7 ms 6996 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 4 ms 4436 KB Output is correct
5 Correct 6 ms 8660 KB Output is correct
6 Correct 35 ms 12884 KB Output is correct
7 Correct 15 ms 14524 KB Output is correct
8 Correct 18 ms 17104 KB Output is correct
9 Correct 19 ms 17188 KB Output is correct
10 Correct 18 ms 16980 KB Output is correct
11 Correct 12 ms 16984 KB Output is correct
12 Correct 18 ms 17108 KB Output is correct
13 Correct 54 ms 17112 KB Output is correct
14 Runtime error 2 ms 388 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -