제출 #681685

#제출 시각아이디문제언어결과실행 시간메모리
681685qwerasdfzxclCigle (COI21_cigle)C++17
100 / 100
234 ms67520 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; int a[5050], dp[5050][5050]; int main(){ int n; scanf("%d", &n); for (int i=1;i<=n;i++) scanf("%d", a+i); for (int s=2;s<=n;s++){ //printf("ok %d\n", s); int L[2] = {a[s-1], a[s]}; int pt[2] = {s-2, s+1}; vector<pair<int, int>> P; while(pt[0] > 0 && pt[1] <= n){ if (pt[0] > 0 && pt[1] <= n && L[0]==L[1]){ P.emplace_back(pt[0], pt[1]); } if (L[0] < L[1]) {L[0] += a[pt[0]]; pt[0]--;} else {L[1] += a[pt[1]]; pt[1]++;} } //if (s==9) for (auto &[x, y]:P) printf(" %d %d\n", x, y); //printf("okok\n"); vector<pair<int, int>> st; ///(count, val) int cnt = 0, pt2 = 0; for (int i=s-1;i>0;i--){ if (pt2<(int)P.size() && P[pt2].first==i) {cnt++; pt2++;} int val = dp[i][s-1] + cnt; if (!st.empty() && (st.back().first < cnt && st.back().second >= val)) continue; if (st.empty() || st.back().first < cnt) st.emplace_back(cnt, val); else if (st.back().second < val) st.back().second = val; } //printf("okokok\n"); pt2 = (int)P.size()-1; for (int j=n;j>=s;j--){ assert(!st.empty()); dp[s][j] = st.back().second; if (pt2 >= 0 && P[pt2].second==j){ cnt = pt2; if (st.back().first == cnt+1){ st.back().first--; st.back().second--; if (st.size() >= 2){ auto p = *++st.rbegin(); if (p.first==cnt){ p.second = max(p.second, st.back().second); st.pop_back(); st.pop_back(); st.push_back(p); } else if (p.second >= st.back().second){ st.pop_back(); } } } --pt2; } } } //printf("%d\n", dp[3][8]); int ans = 0; for (int i=1;i<=n;i++) ans = max(ans, dp[i][n]); printf("%d\n", ans); return 0; }

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

cigle.cpp: In function 'int main()':
cigle.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
cigle.cpp:10:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~
#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...