oj.uz

Submission #404555

# Submission time Handle Problem Language Result Execution time Memory
404555 2021-05-14T15:32:02 Z teehandsome Bali Sculptures (APIO15_sculpture) C++11
0 / 100
 1000 ms 2088 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+1;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 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 588 KB Output is correct
7 Correct 9 ms 588 KB Output is correct
8 Correct 9 ms 716 KB Output is correct
9 Correct 33 ms 740 KB Output is correct
10 Correct 41 ms 640 KB Output is correct
11 Correct 54 ms 672 KB Output is correct
12 Correct 8 ms 700 KB Output is correct
13 Correct 7 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 #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 332 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 9 ms 624 KB Output is correct
8 Correct 9 ms 732 KB Output is correct
9 Correct 33 ms 668 KB Output is correct
10 Correct 43 ms 700 KB Output is correct
11 Correct 41 ms 728 KB Output is correct
12 Correct 8 ms 716 KB Output is correct
13 Correct 7 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 2 ms 332 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 9 ms 588 KB Output is correct
8 Correct 11 ms 744 KB Output is correct
9 Correct 41 ms 740 KB Output is correct
10 Correct 43 ms 648 KB Output is correct
11 Correct 41 ms 660 KB Output is correct
12 Correct 8 ms 716 KB Output is correct
13 Correct 7 ms 716 KB Output is correct
14 Correct 15 ms 804 KB Output is correct
15 Correct 45 ms 956 KB Output is correct
16 Correct 385 ms 1736 KB Output is correct
17 Correct 403 ms 2088 KB Output is correct
18 Execution timed out 1098 ms 1980 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 1 ms 332 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 9 ms 588 KB Output is correct
8 Correct 9 ms 744 KB Output is correct
9 Correct 34 ms 692 KB Output is correct
10 Correct 44 ms 712 KB Output is correct
11 Correct 41 ms 780 KB Output is correct
12 Correct 10 ms 716 KB Output is correct
13 Correct 7 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 588 KB Output is correct
7 Correct 9 ms 636 KB Output is correct
8 Correct 9 ms 664 KB Output is correct
9 Correct 34 ms 736 KB Output is correct
10 Correct 42 ms 696 KB Output is correct
11 Correct 50 ms 748 KB Output is correct
12 Correct 8 ms 716 KB Output is correct
13 Correct 8 ms 740 KB Output is correct
14 Runtime error 2 ms 460 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -