Submission #896075

#	Time	Username	Problem	Language	Result	Execution time	Memory
896075		AgentPengin	Bali Sculptures (APIO15_sculpture)	C++14	100 / 100	280 ms	2904 KiB

sculpture

/**
 *    author:  AgentPengin ( Độc cô cầu bại )
 *    created: 23.12.2022 10:08:02
 *    too lazy to update time
**/
#include<bits/stdc++.h>

#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define int ll

using namespace std;

const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 1e5 + 5;

int n,A,B,pre[2005];

namespace sub1 {
	ll ans = 0;
	bool dp[2009][2009];
	
	bool check(int bit) {
		for (int i = 0;i <= 100;i++) {
			for (int j = 0;j <= 100;j++) dp[i][j] = false;
		}
		dp[0][0]=true;
		for (int i = 0;i < n;i++) {
			for (int j = 0;j <= i;j++) {
				for (int t = i + 1;t <=n;t++) {
					int val = pre[t]-pre[i];
					if (val >> bit & 1 ^ 1 && (val | ans) <= ans + (1LL << bit) - 1) dp[t][j+1] |=dp[i][j];
				}
			}
		}
		for(int j = A;j <= B;j++) {
			if (dp[n][j]) return true;
		}
		return false;
	}
	void solve() {
		for (int bit = 40;bit >= 0;bit--) {
			if (!check(bit)) ans |= (1LL << bit);
		}
		cout << ans;
	}
	
}

namespace sub2 {
	
	ll ans = 0;
	int f[2005];
	
	bool check(int bit) {
		memset(f,0x3f,sizeof f);
		f[0] = 0;
		for (int i = 0;i < n;i++) {
			for (int t = i + 1; t <= n;t++) {
				int val = pre[t] - pre[i];
				if (val >> bit & 1 ^ 1 && (val | ans) <= ans + (1LL << bit) - 1) f[t] = min(f[t],f[i] + 1);
			}
		}	
		return f[n] <= B;
	}
	
	void solve() {
		for(int bit = 40;bit >= 0;bit--) {
			if (!check(bit)) ans |= (1LL << bit);
		}
		cout << ans;
	}
	
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if (ifstream(NAME".inp")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
    cin >> n >> A >> B;
    for (int i = 1;i <= n;i++) {
    	int x; cin >> x;
    	pre[i]=pre[i-1] + x;
    }
    if (n <=100)sub1::solve();
    else sub2::solve();
    
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}
// agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

sculpture.cpp: In function 'bool sub1::check(long long int)':
sculpture.cpp:41:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   41 |      if (val >> bit & 1 ^ 1 && (val | ans) <= ans + (1LL << bit) - 1) dp[t][j+1] |=dp[i][j];
      |          ~~~~~~~~~~~^~~
sculpture.cpp: In function 'bool sub2::check(long long int)':
sculpture.cpp:70:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   70 |     if (val >> bit & 1 ^ 1 && (val | ans) <= ans + (1LL << bit) - 1) f[t] = min(f[t],f[i] + 1);
      |         ~~~~~~~~~~~^~~
sculpture.cpp: In function 'int main()':
sculpture.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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