제출 #285885

#제출 시각아이디문제언어결과실행 시간메모리
285885Dymo포탈들 (BOI14_portals)C++14
0 / 100
1 ms384 KiB
#include<bits/stdc++.h> #define ll long long #define ld long double #define pb push_back #define all(n) n.begin(),n.end() #define eb emplace_back #define endl "\n" #define pll pair<ll,ll> #define ff first #define ss second using namespace std; const ll maxn=2e3+5; const ll mod=998244353; const ll base=1e15; ll ans=0; bool chk(ll p,ll bit) { for (ll i=42; i>=bit; i--) { if ((ans&(1ll<<i))) { } else { if (p&(1ll<<i)) return false; } } return true; } ll dp[maxn][maxn]; ll dp1[maxn][maxn]; ll dp2[maxn]; ll dp3[maxn]; ll f[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); /*if (fopen("terrorists.inp","r")) { freopen("terrorists.inp","r",stdin); freopen("terrorists.out","w",stdout); }*/ ll n, a, b; cin>>n>>a>>b; for (int i=1; i<=n; i++) { ll x; cin>>x; f[i]=f[i-1]+x; } if (n<=100) { for (int i=1; i<=b; i++) { for (int j=i; j<=n; j++) { dp[i][j]=1; } } for (ll bit=42; bit>=0; bit--) { for (int i=1; i<=b; i++) { for (int j=i; j<=n; j++) { dp1[i][j]=dp[i][j]; } } for (int j=1; j<=n; j++) { if (!dp1[1][j]) continue; ll p=f[j]; if (!chk(p,bit)) { dp1[1][j]=0; } } bool kt=false; if (dp1[1][n]&&1>=b) kt=true; for (int i=2; i<=b; i++) { for (int j=i; j<=n; j++) { if (!dp1[i][j]) continue; dp1[i][j]=0; for (int k=j-1; k>=i-1; k--) { if (!dp1[i-1][k]) continue; ll p=f[j]-f[k]; if (chk(p,bit)) { dp1[i][j]=1; break; } } } if (i>=a&&dp1[i][n]) { kt=true; } } if (kt) { for (int i=1; i<=b; i++) { for (int j=i; j<=n; j++) { dp[i][j]=dp1[i][j]; } } } else { ans=ans+(1ll<<bit); } } } else { for (ll bit=42;bit>=0;bit--) { for (int i=0;i<=n;i++) dp2[i]=dp3[i]; for (int i=1;i<=n;i++) { if(dp2[i]==base) continue; dp2[i]=base; for (int j=i-1;j>=0;j--) { if (dp2[j]==base) continue; ll p= f[i]-f[j]; if (chk(p,bit)) { dp2[i]=min(dp2[i],dp2[j]+1); } } if (dp2[i]>b) dp2[i]=base; } if (dp2[n]<=b) { for (int i=0;i<=n;i++) { dp3[i]=dp2[i]; } } else { ans=ans+(1ll<<bit); } } } /* else { }*/ cout <<ans<<endl ; }
#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...