Submission #335449

#TimeUsernameProblemLanguageResultExecution timeMemory
335449SwanBali Sculptures (APIO15_sculpture)C++14
100 / 100
85 ms512 KiB
#include <bits/stdc++.h> #define stop system("pause") #define INP freopen("balance.in","r",stdin) #define OUTP freopen("balance.out","w",stdout) #define int long long using namespace std; int n, a, b; vector<int> v; int dp[2001]; int dp2[101][101]; bool eq(int x, int mask){ //cout << "qwe " << x << ' ' << mask << ' ' << (x & mask) << endl; return (x & mask) == 0; } bool bit(int x, int need){ return x & (1ll << need); } bool check1(int mask, int dig){ for(int i = 0; i < n;i++){ dp[i] = -1; int mnres = INT_MAX; int sum = 0; for(int j = i; j >= 0;j--){ sum+=v[j]; if(eq(sum, mask) && !bit(sum, dig)){ if(i == 0)mnres = 1; else{ if(dp[j - 1] == -1)continue; mnres = min(mnres, dp[j - 1] + 1); } } } if(mnres!=INT_MAX){ dp[i] = mnres; } } if(dp[n - 1] == -1){ return 0; } if(dp[n - 1] > b)return 0; return 1; } bool check2(int mask, int dig){ for(int k = 1; k <= b;k++){ for(int i = 0; i < n;i++){ int sum = 0; dp2[i][k] = -1; for(int j = i; j >= 0;j--){ sum+=v[j]; if(eq(sum, mask) && !bit(sum, dig)){ if(k == 1){ if(j!=0)continue; dp2[i][k] = 1; continue; } if(j == 0 && k!=1)continue; if(dp2[j - 1][k - 1] == -1)continue; dp2[i][k] = 1; } } } } for(int k = a; k <= b;k++){ if(dp2[n - 1][k] != -1)return 1; } return 0; } main(){ ios_base::sync_with_stdio(0); cin >> n >> a >> b; for(int i = 0; i < n;i++){ int x; cin >> x; v.push_back(x); } int mask = 0; int ans = 0; //cout << "che " << (1 << 30) << endl; for(int b = 50; b >= 0;b--){ mask^=(1ll << b); bool f = (n <= 100 ? check2(mask, b) : check1(mask, b)); if(!f){ //cout << "bad " << endl; ans+=(1ll << b); mask^=(1ll << b); } } cout << ans; return 0; } /* 6 1 3 8 1 2 1 5 4 */

Compilation message (stderr)

sculpture.cpp:76:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...