Submission #989708

#	Time	Username	Problem	Language	Result	Execution time	Memory
989708		vjudge1	수열 (APIO14_sequence)	C++17	100 / 100	696 ms	83040 KiB

sequence

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>


using namespace std;

// #define int long long
#define ll long long
#define vec vector<long long>
#define pb push_back
#define sz(a) a.size()
#define fi first
#define se second
#define ret(a) return cout<<(a)<<"\n",void()
#define endl "\n"
#define el cout<<"\n"
#define f(a) for(int i=0;i<(a);i++)
#define f1(a) for(int i=1;i<(a);i++)
#define all(v) v.begin(),v.end()
template<class T> void PRINTARR(T a[], int n){for(int i=0;i<n;i++){std::cout<<a[i]<<" ";}std::cout<<'\n';}
template<class T> void PRINTVEC(std::vector<T> arr){for(int i=0;i<arr.size();i++){std::cout<<arr[i]<<" ";}std::cout << '\n';}

int tc=1;
void input(){
}

const int oo = 1e9+7;
const int maxn = 1e5+10;
const int mod = 1e9+7;
const int S = 360;

//REMEMBER:
//USE LONG LONG WHEN NECESSARY
//ALWAYS USE "\n" OR el;
//PRAGMA?

ll dp[2][maxn];
int trace[203][maxn];
int n,k;
vector<ll> pf;
vector<int> a;

void cal(int cur, int l, int r, int otpl, int otpr){
	if(l>r) return;
	int mid=(l+r)/2;
	int otp;
	for(int k=min(mid,otpr);k>=otpl;k--){
		// update(k,mid);
		ll x = dp[0][k-1] + (pf[mid] - pf[k-1])*(pf[n] - pf[mid]);
		if(x>=dp[1][mid]){
			dp[1][mid]=x;
            trace[cur][mid]=k-1;
			otp=k;
		}
	}
	cal(cur, l,mid-1,otpl,otp);
	cal(cur, mid+1,r,otp,otpr);
}

void solve()
{
	cin>>n>>k;
	a.resize(n+1);
    pf.resize(n+1);
	f1(n+1){
        cin>>a[i];
        pf[i] = a[i];
        pf[i] += pf[i-1];
    }
    for(int i=0;i<203;i++){
        for(int j=0;j<maxn;j++){
            trace[i][j]=-1;
            if(i<2){
                dp[i][j]=-oo;
            }
        }
    }

    for(int i=1;i<=n;i++){
        dp[0][i] = pf[i]*(pf[n]-pf[i]);
        trace[1][i] = 0;
    }

	for(int i=2;i<=k+1;i++){
		cal(i,1,n,1,n);
		for(int j=0;j<=n;j++){
			dp[0][j]=dp[1][j];
			dp[1][j]=-oo;
		}
	}
    cout<<dp[0][n]<<"\n";
    int xx = n, yy=k+1;
    vector<int> sus;
    while(trace[yy][xx]!=-1){
        // cout<<trace[yy][xx]+1<<" ";
        sus.pb(trace[yy][xx]+1);
        xx=trace[yy][xx];
        yy--;
    }
    sus.pop_back();
    reverse(all(sus));
    for(int x:sus)cout<<x-1<<" ";
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

	input();
    while (tc--)
        solve();

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void cal(int, int, int, int, int)':
sequence.cpp:58:5: warning: 'otp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |  cal(cur, l,mid-1,otpl,otp);
      |  ~~~^~~~~~~~~~~~~~~~~~~~~~~

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