Submission #1095862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095862		Requiem	Bali Sculptures (APIO15_sculpture)	C++17	100 / 100	50 ms	1884 KiB

sculpture

#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 false;
        }
        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;
        cerr << cur << endl;
        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 (stderr)

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

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 21 / 21
• Subtask 4: 25 / 25
• Subtask 5: 29 / 29