제출 #790685

#제출 시각아이디문제언어결과실행 시간메모리
790685qwerasdfzxclChorus (JOI23_chorus)C++17
100 / 100
4046 ms59124 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") using namespace std; typedef long long ll; constexpr ll INF = 4e18; char s[2002000]; int a[1001000], b[1001000], nxt[2002000], prv[2002000], r2[1001000]; ll cst[505][505], dp_naive[505][505], sum[1001000]; inline ll cost(int l, int r){ // O(1) if (r2[r] < l) return 0; return (ll)(r+1) * (r2[r]-l+1) - (sum[r2[r]] - sum[l-1]); } ll naive(int n, int k){ for (int i=1;i<=n;i++){ for (int j=i;j<=n;j++){ for (int k=i;k<=j;k++){ cst[i][j] += max(j-nxt[b[k]]+1, 0); } } } for (int i=0;i<=n;i++){ fill(dp_naive[i], dp_naive[i]+k+1, INF); } dp_naive[0][0] = 0; for (int i=1;i<=n;i++){ for (int j=1;j<=k;j++){ for (int p=0;p<i;p++) dp_naive[i][j] = min(dp_naive[i][j], dp_naive[p][j-1] + cst[p+1][i]); } } return dp_naive[n][k]; } ll dp[1001000]; int dp2[1001000]; struct Hull{ vector<int> st, st2; int pt, cap; ll lambda; void init(int n, ll _lambda){ st.clear(); st2.clear(); pt = 0; cap = n; lambda = _lambda; } inline ll calc(int f, int x){ assert(f < x); return dp[f] + cost(f+1, x) * 2 + lambda; } int cross(int f, int g){ int l = g+1, r = cap, ret = cap+1; while(l<=r){ int mid = (l+r)>>1; if (calc(f, mid) > calc(g, mid)) ret = mid, r = mid-1; else l = mid+1; } return ret; } void push(int x){ if (x==cap) return; while(st.size() >= 2 && st2.back() >= x+1 && calc(st.back(), st2.back()) >= calc(x, st2.back())){ st.pop_back(); st2.pop_back(); } if (st.size() >= 1 && calc(st.back(), cap) <= calc(x, cap)) return; if (st.size() >= 1) st2.push_back(cross(st.back(), x)); st.push_back(x); assert(st2.empty() || st2.back() <= cap); } pair<ll, int> query(int x){ pt = min(pt, (int)st.size()-1); while(pt+1<(int)st.size() && st2[pt] <= x) pt++; return {calc(st[pt], x), dp2[st[pt]]+1}; } }hull; int alien(int n, ll lambda){ // y + \lambda x min hull.init(n, lambda); hull.push(0); for (int i=1;i<=n;i++){ auto [val, cnt] = hull.query(i); dp[i] = val; dp2[i] = cnt; hull.push(i); } return dp2[n]; } ll solve(int n, int k){ ll l = 0, r = 1e12 + 100, opt = -1; while(l<=r){ ll mid = (l+r) / 2; int val = alien(n, mid*2-1); if (val==k){ return (dp[n] - (mid*2-1) * val) / 2; } if (val >= k) opt = mid, l = mid+1; else r = mid-1; } assert(opt >= 0); int cnt = alien(n, opt*2-1); ll val = (dp[n] - (opt*2-1) * cnt) / 2; if (cnt==k){ return val; } int cnt2 = alien(n, opt*2+1); ll val2 = (dp[n] - (opt*2+1) * cnt2) / 2; assert(cnt2 < k); return val2 - opt * (k-cnt2); } int main(){ int n, k; scanf("%d %d", &n, &k); hull.st.reserve(n+100); hull.st2.reserve(n+100); scanf("%s", s+1); int ptA = 1, ptB = 1; for (int i=1;i<=n*2;i++){ if (s[i]=='A'){ prv[i] = ptB-1; a[ptA++] = i; } else{ prv[i] = ptB; b[ptB++] = i; } } for (int i=n*2;i;i--){ if (s[i]=='A') nxt[i] = --ptA; else nxt[i] = ptA; } for (int i=1;i<=n;i++) sum[i] = sum[i-1] + nxt[b[i]], r2[i] = min(i, prv[a[i]]); printf("%lld\n", solve(n, k)); }

컴파일 시 표준 에러 (stderr) 메시지

chorus.cpp: In function 'int main()':
chorus.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d %d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  scanf("%s", s+1);
      |  ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...