oj.uz

Submission #1095840

# Submission time Handle Problem Language Result Execution time Memory
1095840 2024-10-03T09:57:14 Z Requiem Bali Sculptures (APIO15_sculpture) C++17
37 / 100
 3 ms 3936 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 = 2e3 + 9;
int n, s1, s2;
int a[MAXN], pre[MAXN];

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 - 1){
            FOR(parts, 0, s2){
                FOR(stateOR, 0, 511){
                    if (dp[i][parts][stateOR]){

                        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 << ' ';
                    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[102][102];

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

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

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

    int dp[2002];

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 0 ms 860 KB Output is correct
8 Correct 0 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 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 972 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 976 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 940 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Runtime error 3 ms 3788 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 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 860 KB Output is correct
12 Correct 0 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 856 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 860 KB Output is correct
18 Correct 0 ms 860 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 0 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 0 ms 860 KB Output is correct
25 Correct 1 ms 856 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 0 ms 860 KB Output is correct
29 Correct 1 ms 972 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 856 KB Output is correct
32 Correct 1 ms 856 KB Output is correct
33 Correct 0 ms 860 KB Output is correct
34 Correct 1 ms 860 KB Output is correct
35 Correct 1 ms 860 KB Output is correct
36 Correct 1 ms 980 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 976 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 0 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 0 ms 860 KB Output is correct
14 Correct 1 ms 1080 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 856 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 1 ms 1884 KB Output is correct
26 Correct 2 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 1996 KB Output is correct
30 Correct 2 ms 1884 KB Output is correct
31 Correct 2 ms 1884 KB Output is correct
32 Correct 2 ms 1884 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 0 ms 856 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 860 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 0 ms 860 KB Output is correct
22 Correct 0 ms 860 KB Output is correct
23 Correct 0 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Runtime error 2 ms 3932 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 1 ms 856 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 0 ms 868 KB Output is correct
6 Correct 1 ms 864 KB Output is correct
7 Correct 1 ms 864 KB Output is correct
8 Correct 0 ms 868 KB Output is correct
9 Correct 0 ms 868 KB Output is correct
10 Correct 1 ms 868 KB Output is correct
11 Correct 1 ms 868 KB Output is correct
12 Correct 1 ms 868 KB Output is correct
13 Correct 0 ms 860 KB Output is correct
14 Runtime error 2 ms 3936 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -