| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 569125 | n0sk1ll | 수열 (APIO14_sequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define erase_uni(x) x.erase(unique(all(x)),x.end())
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
/*using namespace __gnu_pbds;
template <class T> using oset = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template <class T> using omset = tree<T, null_type,less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;*/
//Note to self: Check for overflow
int a[1000005];
li dp[1000005][202];
int gde[1000005][202];
int pre[1000005];
li cost(int l, int r)
{
if (l==1) return pre[r];
return (li)pre[l-1]*(pre[r]-pre[l-1]);
}
void compute(int k, int l, int r, int optl, int optr)
{
if (l>r) return;
int mid=(l+r)/2;
fff(g,optl,min(mid-1,optr))
{
li sta=dp[g][k-1]+cost(g+1,mid);
if (sta>=dp[mid][k]) dp[mid][k]=sta,gde[mid][k]=g;
}
compute(k,l,mid-1,optl,gde[mid][k]);
compute(k,mid+1,r,gde[mid][k],optr);
}
void rekurz(int n, int k)
{
if (k==0) return;
rekurz(gde[n][k],k-1),cout<<max(1,gde[n][k])<<" ";
}
int main()
{
FAST;
int n,k; cin>>n>>k;
fff(i,1,n) cin>>a[i];
fff(i,1,n) pre[i]=pre[i-1]+a[i];
fff(j,1,k) compute(j,1,n,1,n);
/*fff(j,0,k)
{
cout<<j<<": "<<endl;
fff(i,1,n) cout<<dp[i][j]<<" "; cout<<endl;
fff(i,1,n) cout<<gde[i][j]<<" "; cout<<endl<<endl;
}*/
cout<<dp[n][k]<<"\n";
rekurz(n,k);
}
//Note to self: Check for overflow
/*
7 3
4 1 3 4 0 2 3
7 6
4 1 3 4 0 2 3
*/