提出 #65065488

---

ソースコード 拡げる

#pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector")
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define fi first
#define se second
#if 1
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '['; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "]";}
void _print() {cerr << endl << flush;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define DEBUG(x...) cerr << "*["<<__LINE__<<"]\t"<< #x << " = "; _print(x)
template<class T>
istream& operator>>(istream& is, vector<T>& v) {
	int n; is>>n; v.resize(n);
	for(auto &i:v) is>>i;
	return is;
}
template<class T1,class T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
	is>>p.fi>>p.se;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for(const auto &i:v) os<<i<<' ';
	return os;
}
template<class T1,class T2>
ostream& operator<<(ostream& os, const pair<T1,T2>& p) {
	os<<p.fi<<' '<<p.se; return os;
}
#endif
 
#define ll long long
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pi pair<int, int>
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
const int maxn = 2000005;
char s[maxn];
int a[maxn];
int pref[maxn];
int calc(int x) {
    if (x < 0) return (-x + 1 ) / 2;
    return 0;
};

vector<pair<ll, int> > xs[2];
const int N = maxn;
ll minsum[N];
const ll inf = 1e18;
ll cont[N];
ll sumgt[N], sumpar[N], sumcnt[N];
ll sufcont[N];
ll seg;

int n, k;
ll total_count(int pos, int k) {
    if (seg == 0) return 1ll * k * cont[pos];
    ll ans = sufcont[pos];
    ll end = pos + 1ll * k * seg;
    if (end <= n) ans -= sufcont[end];
    return ans;
}
ll final[maxn];
void solve(int kl, int kr, int nl, int nr) {
    if (kl > kr) return;
    int mid = (kl + kr) / 2;
    ll best = inf, bpos = -1;
    for (int i = nl; i <= nr; i++) {
        ll cur = total_count(i, mid) + minsum[i];
        if (cur < best) {
            best = cur;
            bpos = i;
        }
    }
    final[mid] = best;
    solve(kl, mid - 1, nl, bpos);
    solve(mid + 1, kr, bpos, nr);
}
int main() {
    cin >> n >> k;
    n *= 2;
    scanf("%s", s + 1);
    for (int j = 1; j <= n; j++) {
        if (s[j] == 'A') a[j] = 1;
        else a[j] = -1;
        pref[j] = pref[j - 1] + a[j];
    }
    seg = pref[n];
    for (int j = 0; j < 2; j++) {
        ll total = 0;
        for (int i = 0; i <= n; i++) {
            total += calc(pref[i]);
            xs[j].pb({total, -pref[i]});
        }
        sort(xs[j].begin(), xs[j].end());
        // DEBUG(xs[j]);
        vector<pair<ll, int> > nx;
        int mxj = -1;
        for (auto v : xs[j]) {
            if (-v.se > mxj) {
                nx.pb(mp(v.fi, -v.se));
                mxj = max(mxj, -v.se);
            }
        }
        reverse(pref + 1, pref + n + 1);
        xs[j] = nx;
    }
    // DEBUG(xs[0]);
    // DEBUG(xs[1]);
    for (int i = 0; i < N; i++) minsum[i] = inf;
    for (auto u: xs[0])
        for (auto v : xs[1])
            chkmin(minsum[min(n, v.se + u.se)], u.fi + v.fi);
    for (int i = 1; i <= n; i++)
        if (pref[i] > 0) {
            sumgt[pref[i]] += pref[i], 
            sumpar[pref[i]] += 1;
            sumcnt[pref[i]] += 1;
        }
    for (int i = n; i >= 0; i--) {
        sumgt[i] += sumgt[i + 1];
        sumpar[i] += sumpar[i + 2];
        sumcnt[i] += sumcnt[i + 1];
    }

    for (int i = 0; i <= n; i++) {
        cont[i] = sumgt[i] - 1ll * i * sumcnt[i] + sumpar[i + 1];
        cont[i] /= 2;
    }

    for (int i = n; i >= 0; i--) {
        sufcont[i] = cont[i];
        if (i + seg <= n) sufcont[i] += sufcont[i + seg];
    }

    solve(1, k, 0, n);

    for (int i = 1; i <= k; i++) 
        cout << final[i] << '\n';
        
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:114:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  114 |     scanf("%s", s + 1);
      |     ~~~~~^~~~~~~~~~~~~

ジャッジ結果