QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#873018 | #9229. Juliet Unifies Ones | emersonjr02 | WA | 1ms | 3584kb | C++17 | 2.4kb | 2025-01-26 07:37:08 | 2025-01-26 07:37:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define sws std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long int
#define float long double
#define ld long double
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define vpii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tiii tuple<int, int, int>
const int MAX = 1e7+10;
const int INF = INT32_MAX;
int MOD = 998244353;
const int LOG = 31;
const ld PI = acos(-1);
const int MINF = INT32_MIN;
vector<pii> dirs = {
{1, 0}, {-1, 0}, {0, 1}, {0, -1},
{1, 1}, {-1, 1}, {1, -1}, {-1, -1},
};
int binexp(int a, int b) {
int res = 1;
while (b) {
if (b&1) res = (res*a)%MOD;
a = (a*a)%MOD;
b >>= 1;
}
return res;
}
void solve() {
string s; cin >> s;
int last = -1, cntLast = 0, ans = 0;
bool flag = false;
vector<pair<int, int>> v;
for(int i = 0; i < s.size(); i++){
if(s[i] - '0' != last){
if(flag) v.push_back({last, cntLast});
cntLast = 0;
if(s[i] - '0' == 1) flag = true;
}
cntLast++;
last = s[i] - '0';
}
if(last == 1) v.push_back({last, cntLast});
vvi memo(52, vi(2, INF));
memo[0][0] = 0;
for(int i = 0; i < v.size(); i++){
for(int j = 0; j < 2; j++){
if(memo[i][j] == INF) continue;
if(j && v[i].first == 1) memo[i+2][j] = min(memo[i+2][j], memo[i][j] + v[i].second);
if(j && !v[i].first) memo[i+1][j] = min(memo[i+1][j], memo[i][j]);
if(!j && v[i].first == 1){
memo[i+2][j] = min(memo[i+2][j], memo[i][j] + v[i].second);
memo[i+1][j] = min(memo[i+1][j], memo[i][j]);
}
if(!j && !v[i].first){
memo[i+1][j] = min(memo[i+1][j], memo[i][j] + v[i].second);
memo[i+1][1] = min(memo[i+1][1], memo[i][j]);
}
}
}
int n = v.size();
cout << min(min(memo[n][1], memo[n][0]), min(memo[n+1][1], memo[n+1][0])) << '\n';
}
signed main(){
int t = 1;
// cin >> t;
while(t--)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3456kb
input:
00011011001
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
input:
11101111111111111101001011110111111110011101010110
output:
10
result:
wrong answer 1st numbers differ - expected: '11', found: '10'