oj.uz

Submission #404552

# Submission time Handle Problem Language Result Execution time Memory
404552 2021-05-14T15:29:12 Z teehandsome Bali Sculptures (APIO15_sculpture) C++11
0 / 100
 1000 ms 1956 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=101;
const int mxg=101;
const int mxv=2001;
int n,a,b;
bool dp[mxn][mxg][mxv];
ll sum[mxn];
vector<int> ar;

ll f(int l,int r) {
    if(!l) return sum[r];
    return sum[r]-sum[l-1];
}



int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>a>>b;
    ar.resize(n);
    for(int i=0;i<n;i++) cin>>ar[i];

    for(int i=0;i<n;i++) {
        sum[i]=ar[i];
        if(i) sum[i]+=sum[i-1];
        dp[i][1][sum[i]]=true;
    }
    for(int i=1;i<n;i++) {
        for(int g=2;g<=i;g++) {
            for(int k=1;k<=sum[i];k++) {
                for(int j=i-1;j>=0;j--) {
                    for(int val=0;val<=sum[j];val++) {
                        if(dp[j][g-1][val] and (val|f(j+1,i))==k) {
//                            debug(val,f(j+1,i),val|f(j+1,i),k);
                            dp[i][g][k]=true; goto newK;
                        }
                    }
                }
                newK:;
            }
        }
    }
    ll ans=1e16;
    for(int i=a;i<=b;i++) {
        for(ll j=0;j<=sum[n-1];j++) {
            if(dp[n-1][i][j]) {
                ans=min(ans,j);
                break;
            }
        }
    }

    cout<<ans<<endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 8 ms 568 KB Output is correct
8 Correct 7 ms 704 KB Output is correct
9 Correct 30 ms 664 KB Output is correct
10 Correct 38 ms 704 KB Output is correct
11 Correct 40 ms 708 KB Output is correct
12 Correct 7 ms 712 KB Output is correct
13 Correct 7 ms 724 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Incorrect 1 ms 320 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 8 ms 588 KB Output is correct
8 Correct 8 ms 716 KB Output is correct
9 Correct 30 ms 696 KB Output is correct
10 Correct 38 ms 692 KB Output is correct
11 Correct 38 ms 672 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 6 ms 716 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 8 ms 588 KB Output is correct
8 Correct 7 ms 716 KB Output is correct
9 Correct 31 ms 696 KB Output is correct
10 Correct 38 ms 692 KB Output is correct
11 Correct 38 ms 696 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 10 ms 704 KB Output is correct
14 Correct 14 ms 716 KB Output is correct
15 Correct 37 ms 948 KB Output is correct
16 Correct 347 ms 1764 KB Output is correct
17 Correct 342 ms 1956 KB Output is correct
18 Execution timed out 1099 ms 1904 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 8 ms 572 KB Output is correct
8 Correct 10 ms 716 KB Output is correct
9 Correct 30 ms 716 KB Output is correct
10 Correct 43 ms 708 KB Output is correct
11 Correct 39 ms 660 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 9 ms 716 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 8 ms 584 KB Output is correct
8 Correct 9 ms 716 KB Output is correct
9 Correct 31 ms 636 KB Output is correct
10 Correct 39 ms 668 KB Output is correct
11 Correct 39 ms 644 KB Output is correct
12 Correct 7 ms 716 KB Output is correct
13 Correct 7 ms 716 KB Output is correct
14 Runtime error 2 ms 460 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -