oj.uz

Submission #1095860

# Submission time Handle Problem Language Result Execution time Memory
1095860 2024-10-03T10:40:03 Z Requiem Bali Sculptures (APIO15_sculpture) C++17
46 / 100
 4 ms 3932 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "sculpture"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

const int MAXN = 3e3 + 9;
int n, s1, s2;
int a[MAXN], pre[MAXN];

namespace subtask1{
    bool check(){
        return n <= 20;
    }

    int res = inf;

    void backtrack(int pos,int curOR, int curPart){
//        cout << pos << ' ' << curOR << ' ' << curPart << endl;
        if (curPart > s2) return;
        if (pos == n){
            if (curPart >= s1) minimize(res, curOR);
            return;
        }
        FOR(nxt, pos + 1, n){
            backtrack(nxt, curOR | (pre[nxt] - pre[pos]), curPart + 1);
        }
    }

    void solve(){
        backtrack(0, 0, 0);
        cout << res << endl;
    }
}
namespace subtask2{
    bool check(){
        FOR(i, 1, n){
            if (a[i] > 10) return false;
        }
        return n <= 50;
    }

    bool dp[53][23][513];
    void solve(){
        memset(dp, false, sizeof(dp));
        dp[0][0][0] = true;
        FOR(i, 0, n){
            FOR(parts, 0, min(i, s2)){
                FOR(stateOR, 0, 511){
                    if (dp[i][parts][stateOR]){
//                        cout << i << ' ' << parts << ' ' << stateOR << endl;
                        FOR(nxt, i + 1, n){
                            int s = pre[nxt] - pre[i];
                            dp[nxt][parts + 1][stateOR | s] = 1;
                        }
                    }
                }
            }
        }

        FOR(state, 0, 511){
            FOR(i, s1, s2){
                if (dp[n][i][state]) {
                    cout << state << endl;
                    return;
                }
            }
        }

    }
}

namespace subtask3{
    bool check(){
        FOR(i, 1, n){
            if (a[i] > 20) return true;
        }
        return (s1 == 1 and n <= 100);
    }

    int dp[102][2059];

    void solve(){
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        FOR(i, 0, n - 1){
            FOR(stateOR, 0, 2047){
                if (dp[i][stateOR] < 1e9){
                    FOR(nxt, i + 1, n){
                        minimize(dp[nxt][stateOR | (pre[nxt] - pre[i])], dp[i][stateOR] + 1);
                    }
                }
            }
        }

        FOR(state, 0, 2047){
            if (dp[n][state] <= s2) {
                cout << state << endl;
                return;
            }
        }
    }
}

namespace subtask4{
    bool check(){
        return n <= 100;
    }

    bool dp[302][302];

    bool can(int msk){
        memset(dp, false, sizeof(dp));
        dp[0][0] = true;
        FOR(i, 1, n){
            FOR(j, 1, min(i, s2)){

                FOR(k, 0, i - 1){
                    int s = pre[i] - pre[k];
                    if ((s & msk) == s) dp[i][j] |= dp[k][j - 1];
                }
//                if (msk == 11 and dp[i][j]) cout << i << ' ' << j << endl;
            }
        }
        FOR(i, s1, s2){
            if (dp[n][i]) return true;
        }
        return false;
    }
    void solve(){
        int cur = (1LL << 43) - 1;
        FORD(i, 42, 0){
            if (can(cur ^ (1LL << i))){
                cur ^= (1LL << i);
            }
//            cout << cur << endl;
        }
        cout << cur << endl;
    }
}

namespace subtask5{
    bool check(){
        return s1 == 1;
    }

    int dp[3010];

    bool can(int msk){
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        FOR(i, 1, n){
            FORD(j, i - 1, 0){
                int s = pre[i] - pre[j];
                if ((s & msk) == s) minimize(dp[i] , dp[j] + 1);
            }
        }
        return dp[n] <= s2;
    }
    void solve(){
        int cur = (1LL << 43) - 1;
        FORD(i, 42, 0){
            if (can(cur ^ (1LL << i))){
                cur ^= (1LL << i);
            }
        }
        cout << cur << endl;
    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> s1 >> s2;
    FOR(i, 1, n){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
    if (subtask4::check()) return subtask4::solve(), 0;
    if (subtask5::check()) return subtask5::solve(), 0;
}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

sculpture.cpp:185:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  185 | main()
      | ^~~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 4 ms 344 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 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 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 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 3 ms 344 KB Output is correct
34 Correct 3 ms 464 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 3 ms 460 KB Output is correct

Subtask #2
16.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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 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 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 ms 408 KB Output is correct
27 Correct 0 ms 860 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 0 ms 860 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 856 KB Output is correct
34 Correct 1 ms 856 KB Output is correct
35 Correct 1 ms 860 KB Output is correct
36 Correct 1 ms 860 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 1 ms 1088 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 1 ms 1884 KB Output is correct
25 Correct 2 ms 1884 KB Output is correct
26 Correct 1 ms 1884 KB Output is correct
27 Correct 2 ms 1884 KB Output is correct
28 Correct 2 ms 1884 KB Output is correct
29 Correct 2 ms 1884 KB Output is correct
30 Correct 2 ms 2112 KB Output is correct
31 Correct 2 ms 1884 KB Output is correct
32 Correct 2 ms 1880 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 ms 468 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 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 3 ms 600 KB Output is correct
34 Correct 3 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 3 ms 472 KB Output is correct
37 Correct 0 ms 860 KB Output is correct
38 Correct 1 ms 860 KB Output is correct
39 Correct 1 ms 860 KB Output is correct
40 Correct 1 ms 1084 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 2 ms 860 KB Output is correct
43 Correct 1 ms 860 KB Output is correct
44 Correct 1 ms 860 KB Output is correct
45 Correct 1 ms 860 KB Output is correct
46 Correct 1 ms 860 KB Output is correct
47 Correct 1 ms 1884 KB Output is correct
48 Correct 1 ms 1884 KB Output is correct
49 Correct 2 ms 2112 KB Output is correct
50 Correct 2 ms 1884 KB Output is correct
51 Correct 2 ms 1880 KB Output is correct
52 Correct 2 ms 1884 KB Output is correct
53 Correct 2 ms 1884 KB Output is correct
54 Correct 3 ms 1884 KB Output is correct
55 Correct 2 ms 1884 KB Output is correct
56 Runtime error 2 ms 3928 KB Execution killed with signal 11
57 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 3 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 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 3 ms 348 KB Output is correct
21 Correct 3 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 3 ms 464 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 0 ms 860 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 856 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 1884 KB Output is correct
35 Correct 1 ms 1884 KB Output is correct
36 Correct 2 ms 1884 KB Output is correct
37 Correct 2 ms 1884 KB Output is correct
38 Correct 2 ms 1884 KB Output is correct
39 Correct 2 ms 1884 KB Output is correct
40 Correct 2 ms 1884 KB Output is correct
41 Correct 2 ms 1884 KB Output is correct
42 Correct 2 ms 1884 KB Output is correct
43 Runtime error 2 ms 3932 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -