oj.uz

Submission #735330

# Submission time Handle Problem Language Result Execution time Memory
735330 2023-05-04T02:31:58 Z ReLice Bali Sculptures (APIO15_sculpture) C++14
37 / 100
 11 ms 448 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl "\n"
#define fr first
#define sc second
#define sz size()
#define bc back()
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}*/
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e9+7;
const ll mod=1e9+7;
const ll N=2e3+7;
ll pref[N],n,l,r;
vector<vector<ll> > g(N);
ll vis[N];
ll d[N];
bool check(ll val){
    deque <pair<ll,ll>> q;
    q.pb({0,1});
    for(ll i=1;i<=n+1;i++) d[i]=inf;
    d[1]=0;
    while(!q.empty()){
        ll x=q.front().sc;
        q.pop_front();
        for(auto i : g[x]){
            if((pref[i]-pref[x-1]) & (1ll<<val)) continue;
            if(d[x]+1<d[i+1]){
                d[i+1]=d[x]+1;
                q.pb({d[i+1],i+1});
            }
        }
    }
    ll l1=d[n+1],r1;
    q.pb({0,1});
    for(ll i=1;i<=n+1;i++) d[i]=inf;
    d[1]=0;
    while(!q.empty()){
        ll x=q.front().sc;
        q.pop_front();
        for(auto i : g[x]){
            if((pref[i]-pref[x-1]) & (1ll<<val)) continue;
            if(d[x]-1<d[i+1]){
                d[i+1]=d[x]-1;
                q.push_front({d[i+1],i+1});
            }
        }
    }
    r1=-d[n+1];
    if(r1<l || l1>r || l1==inf || r1==inf) return false;
    else return true;
}
void ers(ll val){
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<g[i].sz;j++){
            if((pref[g[i][j]]-pref[i-1]) & (1ll<<val)){
                swap(g[i][j],g[i].bc);
                g[i].pop_back();
                j--;
            }
        }
    }
}
void solve(){
    ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
    ll k;
    cin>>n>>l>>r;
    vector <ll> v;
    v.pb(0);
    for(i=0;i<n;i++){
        cin>>b;
        v.pb(b);
    }
    for(i=1;i<=n;i++){
        pref[i]=pref[i-1]+v[i];
    }
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
            g[i].pb(j);
        }
    }
    for(i=30;i>=0;i--){
        if(check(i)){
            ers(i);
        }
        else{
            ans+=(1ll<<i);
        }
    }
    cout<<ans<<endl;

}
signed main(){
    //start();
    //fre("");
    ll t=1;
    //cin>>t;
    while(t--) solve();
}
/*
6 1 3
8 1 2 1 5 4
*/

Compilation message

sculpture.cpp: In function 'void ers(long long int)':
sculpture.cpp:66:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(ll j=0;j<g[i].sz;j++){
      |                     ^
sculpture.cpp: In function 'void solve()':
sculpture.cpp:76:12: warning: unused variable 'q' [-Wunused-variable]
   76 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |            ^
sculpture.cpp:76:14: warning: unused variable 'sum' [-Wunused-variable]
   76 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |              ^~~
sculpture.cpp:76:28: warning: unused variable 'mx' [-Wunused-variable]
   76 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                            ^~
sculpture.cpp:76:34: warning: unused variable 'c' [-Wunused-variable]
   76 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                                  ^
sculpture.cpp:76:38: warning: unused variable 'm' [-Wunused-variable]
   76 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                                      ^
sculpture.cpp:76:40: warning: unused variable 't' [-Wunused-variable]
   76 |     ll i,j,q,sum=0,ans=0,b,mx=-1,c=1,m,t;
      |                                        ^
sculpture.cpp:77:8: warning: unused variable 'k' [-Wunused-variable]
   77 |     ll k;
      |        ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Incorrect 1 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 3 ms 340 KB Output is correct
34 Correct 2 ms 368 KB Output is correct
35 Correct 2 ms 340 KB Output is correct
36 Correct 3 ms 340 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 2 ms 340 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 3 ms 340 KB Output is correct
26 Correct 4 ms 340 KB Output is correct
27 Correct 6 ms 340 KB Output is correct
28 Correct 10 ms 340 KB Output is correct
29 Correct 8 ms 416 KB Output is correct
30 Correct 11 ms 416 KB Output is correct
31 Correct 8 ms 412 KB Output is correct
32 Correct 8 ms 412 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 1 ms 340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -