Submission #877380

#	Time	Username	Problem	Language	Result	Execution time	Memory
877380		winter0101	Lamps (JOI19_lamps)	C++14	100 / 100	91 ms	35792 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e6+9;
int f[maxn][3][2];
int a[maxn],b[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    s=" "+s;
    t=" "+t;
    for1(i,1,n){
    if (s[i]=='1')a[i]=1;
    if (t[i]=='1')b[i]=1;
    }
    for1(i,0,n){
    for1(j,0,2){
    for1(k,0,1){
    f[i][j][k]=n+1;
    }
    }
    }
    f[0][0][0]=0;
    //turn on/off ? then toggle later
    //1 on 2 off
    for1(i,1,n){
    for1(newj,0,2){
    for1(newk,0,1){
    for1(j,0,2){
    for1(k,0,1){
    int cost=(f[i-1][j][k]+(j!=newj&&newj!=0)+(k!=newk&&newk==1));
    int newa=a[i];
    if (newj==1)newa=1;
    if (newj==2)newa=0;
    if (newk==1)newa=1-newa;
    if (newa!=b[i])continue;
    f[i][newj][newk]=min(f[i][newj][newk],cost);
    }
    }
    }
    }
    }
    int ans=n+1;
    for1(j,0,2)for1(k,0,1)ans=min(ans,f[n][j][k]);
    cout<<ans;

}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49