QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#873018#9229. Juliet Unifies Onesemersonjr02WA 1ms3584kbC++172.4kb2025-01-26 07:37:082025-01-26 07:37:08

Judging History

你现在查看的是最新测评结果

  • [2025-01-26 07:37:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3584kb
  • [2025-01-26 07:37:08]
  • 提交

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();
}

詳細信息

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'