# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
170517 | 2019-12-25T14:39:30 Z | Swan | Bali Sculptures (APIO15_sculpture) | C++14 | 4 ms | 2552 KB |
#include <bits/stdc++.h> #define stop system("pause") #define stop2 char o; cin >> o #define INP freopen("pcb.in","r",stdin) #define OUTP freopen ("pcb.out","w",stdout) #define int long long using namespace std; const int maxn = 210; set<int> dp[maxn][maxn]; int ans[maxn][maxn]; void prosev(int x,int y){ vector<int> bad; vector<int> now; for(auto&a : dp[x][y])now.push_back(a); for(int i(0); i < now.size();i++){ for(int j(0); j < now.size();j++){ if(i == j)continue; int kek = now[i]^(now[i]|now[j]); if(kek){ bad.push_back(i); break; } } } for(int i(0); i < bad.size();i++){ dp[x][y].erase(dp[x][y].find(now[bad[i]])); } } main(){ ios_base::sync_with_stdio(0); int n,a,b; cin >> n >> a >> b; vector<int> v; v.push_back(0); srand(time(0)); for(int i(1); i <= n;i++){ int x; cin >> x; v.push_back(x); } dp[0][0].insert(0); for(int i(0);i<=n;i++){ for(int j(0);j<=n;j++){ ans[i][j] = 1e16; } } for(int k(1);k<=b;k++){ for(int i(1); i <=n;i++){ int sum = 0; //cout << k << ' ' << i << ' ' << ans[k][i] << endl; for(int to(i);to > 0;to--){ sum+=v[to]; for(auto&a : dp[k-1][to-1]){ dp[k][i].insert(sum|a); ans[k][i] = min(ans[k][i],(sum|a)); } } //cout << k << ' ' << i << ' ' << ans[k][i] << endl; prosev(k,i); } } int res = 1e17; for(int i(a);i<=b;i++){ //cout << i << ' ' << ans[i][n] << endl; res = min(res,ans[i][n]); } cout << res; } /* 6 1 3 8 1 2 1 5 4 100 1 100 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2552 KB | Output is correct |
2 | Incorrect | 4 ms | 2424 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2424 KB | Output is correct |
2 | Incorrect | 4 ms | 2424 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2552 KB | Output is correct |
2 | Incorrect | 4 ms | 2468 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2424 KB | Output is correct |
2 | Incorrect | 4 ms | 2424 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 2428 KB | Output is correct |
2 | Incorrect | 4 ms | 2552 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |