QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397888 | #69. Lamps | Rafi22 | 0 | 7ms | 14524kb | C++14 | 1.2kb | 2024-04-24 19:08:47 | 2024-04-24 19:08:47 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;
const int N=1000007;
int DP[N];
int id[N];
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
string a,b;
cin>>a>>b;
a='#'+a,b='#'+b;
vector<pair<int,int>>V;
int l=-1,it=0;
for(int i=1;i<=n;i++)
{
if(b[i]!=b[i-1]) it++;
id[i]=it;
// cout<<id[i]<<" ";
if(a[i]!=b[i])
{
if(l==-1) l=i;
}
else if(l!=-1)
{
V.pb({l,i-1});
l=-1;
}
}
// cout<<endl;
if(l!=-1) V.pb({l,n});
// for(auto [a,b]:V) cout<<a<<" "<<b<<endl;
int m=sz(V);
//cout<<m<<endl;
for(int i=1;i<=m;i++)
{
DP[i]=DP[i-1];
for(int j=0;j<i;j++)
{
DP[i]=max(DP[i],DP[j]+(i-j)-(id[V[i-1].nd]-id[V[j].st]+1)/2-1);
}
}
cout<<m-DP[m];
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 3632kb
input:
1 1 0
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 10 01
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 01 10
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 11 00
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 11 10
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 11 01
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
18 000000000000000000 101010101010101010
output:
9
result:
ok single line: '9'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
18 111111111111111111 010101010101010101
output:
9
result:
ok single line: '9'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
17 11111111111111111 10101010101010101
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
17 00000000000000000 01010101010101010
output:
8
result:
ok single line: '8'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
18 110111100010101111 010111100011100000
output:
3
result:
ok single line: '3'
Test #13:
score: -6
Wrong Answer
time: 0ms
memory: 3564kb
input:
17 10110110110110101 01011100100110000
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #59:
score: 4
Accepted
time: 0ms
memory: 3624kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #60:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 0 1
output:
1
result:
ok single line: '1'
Test #61:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 00 00
output:
0
result:
ok single line: '0'
Test #62:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 00 10
output:
1
result:
ok single line: '1'
Test #63:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 00 01
output:
1
result:
ok single line: '1'
Test #64:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 00 11
output:
1
result:
ok single line: '1'
Test #65:
score: 0
Accepted
time: 7ms
memory: 14524kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok single line: '0'
Test #66:
score: -4
Time Limit Exceeded
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%