oj.uz

Submission #199210

# Submission time Handle Problem Language Result Execution time Memory
199210 2020-01-30T09:35:32 Z Alexa2001 Bali Sculptures (APIO15_sculpture) C++17
37 / 100
 1000 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
const int Nmax = 2005;


int dp[Nmax];
bitset<Nmax> can[Nmax];
int n, A, B;

ll s[Nmax];


bool check1(ll mask)
{
    int i, j;
    for(i=1; i<=n; ++i)
    {
        dp[i] = 1e9;
        for(j=0; j<i; ++j)
            if( ((s[i] - s[j]) | mask) == mask )
                dp[i] = min(dp[i], dp[j] + 1);
    }

    return dp[n] <= B;
}

bool check2(ll mask)
{
    int i, j, k;

    can[0][0] = 1;
    for(i=1; i<=n; ++i)
        {
            for(j=1; j<=B; ++j) can[i][j] = 0;

            for(k=0; k<i; ++k)
                if( ((s[i] - s[k]) | mask) == mask)
                    for(j=1; j<=B; ++j)
                        can[i][j] = can[i][j] | can[k][j-1];
        }

    for(i=A; i<=B; ++i)
        if(can[n][i]) return 1;
    return 0;
}

bool check(ll mask)
{
    if(A == 1) return check1(mask);
        else return check2(mask);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    int i;
    cin >> n >> A >> B;
    for(i=1; i<=n; ++i) cin >> s[i], s[i] += s[i-1];

    for(i=0; (1<<i) <= s[n]; ++i); --i;

    ll ans = (1<<(i+1)) - 1;

    for(; i>=0; --i)
        if(check(ans ^ (1<<i)))
            ans ^= (1<<i);

    cout << ans << '\n';
    return 0;
}

Compilation message

sculpture.cpp: In function 'int main()':
sculpture.cpp:66:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=0; (1<<i) <= s[n]; ++i); --i;
     ^~~
sculpture.cpp:66:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=0; (1<<i) <= s[n]; ++i); --i;
                                    ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 380 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 380 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Execution timed out 1089 ms 376 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 372 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 380 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 6 ms 376 KB Output is correct
27 Correct 5 ms 380 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 376 KB Output is correct
35 Correct 5 ms 376 KB Output is correct
36 Correct 5 ms 376 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 372 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 428 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 296 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 6 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 5 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 5 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 380 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Execution timed out 1091 ms 376 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Execution timed out 1082 ms 376 KB Time limit exceeded
15 Halted 0 ms 0 KB -