제출 #855292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855292		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	2099 ms	3528 KiB

sequence

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <unordered_set>

#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(all(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(all(v),x)-v.begin())

const int N = 1e5 + 78 , inf = 1e18 , M = 1e9 + 7;
using namespace std;

string trans(int n , int k){
    string s = "";
    while(n != 0){
        int d = n % k;
        if(d < 10){
            s = to_string(d) + s;
        }
        else{
            s = char(d + 'A' - 10) + s;
        }
        n /= k;
    }
    return s;
}
int pref[N] , suff[N] , suff1[N] , suff2[N];
pii dp[N];
void solve(){
	int n , k;
	cin >> n >> k;
	int a[n + 1];
	vector<int> ans;
	int mx = 0;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	for(int i = n ; i >= 1 ; i--)suff[i] = suff[i + 1] + a[i];
   for(int i = 0 ; i < pow(2 , n) ; i++){
        int cnt = i , c = 0;
		string s = trans(i , 2);
        while(s.size() != n){
            s += '0';
        }
        int ss = 0 , lst = 0;
        vector<int> v;
		for(int j = 0 ; j < len(s) ; j++){
			if(s[j] == '1'){
				ss += (pref[j + 1] - pref[lst]) * suff[j + 2];
				lst = j + 1;
				v.pb(j + 1);
			}
		}
		if(mx < ss and len(v) == k){
			mx = ss;
			ans.clear();
			for(auto it : v)ans.pb(it);
		}
    }
    cout << mx << '\n';
    for(auto it : ans)cout << it << ' ';
}

signed main(){
    Bekabot
    int t = 1;
    //cin >> t;
    while(t--){
		solve();
	}
}

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

sequence.cpp: In function 'void solve()':
sequence.cpp:61:24: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   61 |         while(s.size() != n){
      |               ~~~~~~~~~^~~~
sequence.cpp:59:13: warning: unused variable 'cnt' [-Wunused-variable]
   59 |         int cnt = i , c = 0;
      |             ^~~
sequence.cpp:59:23: warning: unused variable 'c' [-Wunused-variable]
   59 |         int cnt = i , c = 0;
      |                       ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29