結果

問題 No.2553 Holidays
コンテスト
ユーザー Lê Hoàng Ngô
提出日時 2024-07-02 12:41:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,735 bytes
コンパイル時間 1,993 ms
コンパイル使用メモリ 177,312 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 12:41:20
合計ジャッジ時間 3,919 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep_r(i,a,b) for(int i=a;i>=b;i--)
#define each(a,x) for (auto& x : a)
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define sz(x) int(x.size())
#define so(x) sort(all(x))
#define so_r(x) sort(all(x),greater<int>())
#define lb lower_bound
#define ub upper_bound
const char nl = '\n';
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int bit_cnt(int x){
    return __builtin_popcount(x);
}
ll bex(ll a, ll b, ll mod = 1e9 + 7){ll res = 1LL; while(b){ if (b&1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

const int MOD = 998244353;
const int N = 1e5 + 5;
const ll INF = 1e16;
vector<int> segments[6];
void solve(){
    int n,m; cin >> n >> m;
    string s; cin >> s;
    s = "x" + s + "x";
    for (int i = 0; i <= n + 1; i++){
        if (s[i] == '-'){
            int st_pos = i;
            char st = s[i-1];
            while (s[i] == '-') i++; 
            char ed = s[i];
            int len = i - st_pos;
            if (st == ed) {
                if (st == 'x') {
                    // type 0: xx with even length
                    if (len % 2 == 0) segments[0].push_back(len); 
                    // type 1: xx with odd length
                    else segments[1].push_back(len);
                } else {
                    // type 2: oo with even length
                    if (len % 2 == 0) segments[2].push_back(len);
                    // type 3: oo with odd length
                    else segments[3].push_back(len);
                }
            } else {
                if (len % 2 == 0) segments[4].push_back(len); // xo or ox with even length
                else segments[5].push_back(len);  // xo or ox with odd length
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += s[i] == 'o';
    so(segments[3]);
    each(segments[3], seg) {
        // cout<<"oo: "<<seg<<nl;
        while (m && seg > 1){
            m--;
            seg -= 2;
            ans += 2;
        }
        if (seg==1) ans++;
    }
    each(segments[2], seg) {
        while (m && seg > 0) {
            m--;
            seg -= 2;
            ans += 2;
        }
    }   
    int extra = 0;
    each(segments[4], seg) {
        while (m && seg > 0) {
            m--;
            seg -= 2;
            ans += 2; 
        }
    }
    each(segments[5], seg) {
        while (m && seg > 1) {
            m--; 
            seg -= 2;
            ans += 2; 
        }
        if (seg==1) extra++;
    }
    so_r(segments[1]);
    each(segments[1], seg) {
        // cout<<"xx: "<<seg<<nl;
        if (seg == 1) {
            extra++; 
            continue;
        }
        int cover = 0;
        if (m) m--, ans++, seg--, cover++;
        if (m) m--, ans++, seg--, cover++;
        while (m && seg > 1){
            m--;
            seg -= 2;
            ans += 2;
        }
        if (cover==2) ++ans;
    }

    so_r(segments[0]);
    each(segments[0], seg) {
        if (seg == 2) {
            extra += 2;
            continue;
        }
        if (m) m--, ans++, seg--;
        while (m && seg > 1) {
            m--; 
            seg -= 2;
            ans += 2; 
        }
        if (seg==1) extra++;
    }
    ans += min(extra, m);
    cout<<ans<<nl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1; 
    // cin >> t;

    while (t--){
        solve();
    }
}
0