제출 #1365147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365147		po_rag526	수열 (APIO14_sequence)	C++20	11 / 100	108 ms	452 KiB

sequence

//
//  main.cpp
//  IntensiveCamp 1 2026
//
//  Created by Ali AlSalman on 27/04/2026.
//

#include <bits/stdc++.h>


//#define INTERACTIVE
//#define TESTCASES
//#define SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__

#ifndef INTERACTIVE
#define endl '\n'
#endif

template<typename T>
using vec = std::vector<T>;
using namespace std;

void solve() {
    int n, k;
    cin>>n>>k;
    vec<int> arr(n);
    for (auto &a : arr) cin>>a;
    
    vec<int> P(n + 1);
    for (int i = 1; i <= n; i++)
        P[i] = P[i - 1] + arr[i - 1];
    
    tuple<long long, vec<int>> ans{-1, {}};
    for (int mask = 0; mask < (1<<n); mask++) if (__builtin_popcount(mask) == k && !(mask>>(n - 1)&1)) {
        vec<int> cuts;
        for (int i = 0; i < n - 1; i++) if ((mask>>i)&1) cuts.push_back(i + 1);
        do {
            long long lans = 0;
            set<int> bounds{0, n};
            for (auto c : cuts) {
                auto up = bounds.upper_bound(c), lo = prev(up);
                lans += (P[*up] - P[c]) * (P[c] - P[*lo]);
                bounds.insert(c);
            }
            ans = max(ans, {lans, cuts});
        } while (next_permutation(cuts.begin(), cuts.end()));
    }
    
    cout<<get<0>(ans)<<endl;
    for (auto c : get<1>(ans)) cout<<c<<" "; cout<<endl;
}

int main() {
#ifndef INTERACTIVE
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
    
    int t = 1;
#ifdef TESTCASES
    cin>>t;
#endif
    
    for (int i = t; i--;) {
#if defined(TESTCASES) && defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
        cout<<"Case "<<t-i<<":\n";
#elif defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
#warning SPOJ_BULLSCHEI�E__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
#endif
        solve();
    }
    return 0;
}

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

sequence.cpp:67:69: warning: missing terminating ' character
   67 | #warning SPOJ_BULLSCHEI�E__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
      |                                                                     ^

• 서브태스크 1: 11 / 11
• 서브태스크 2: 0 / 11
• 서브태스크 3: 0 / 11
• 서브태스크 4: 0 / 17
• 서브태스크 5: 0 / 21
• 서브태스크 6: 0 / 29