제출 #681685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681685		qwerasdfzxcl	Cigle (COI21_cigle)	C++17	100 / 100	234 ms	67520 KiB

cigle

#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);
      |                            ~~~~~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52