| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 137935 | 2019-07-28T14:35:24 Z | mahmoudbadawy | 수열 (APIO14_sequence) | C++17 | 276 ms | 18780 KB |
#include <bits/stdc++.h>
using namespace std;
struct line
{
long long m,c;
double x;
int ind;
int isq;
line():m(0),c(0),isq(0),x(0),ind(0){}
line(long long m,long long c,int ind):m(m),c(c),isq(0),x(0),ind(ind){}
bool operator<(const line &other) const
{
if(isq||other.isq) return x<other.x;
if(m==other.m) return ind<other.ind;
return m<other.m;
}
};
struct convex_hull
{
set<line> ss;
set<line>::iterator prev(set<line>::iterator it)
{
return --it;
}
set<line>::iterator next(set<line>::iterator it)
{
return ++it;
}
bool hasprev(set<line>::iterator it)
{
return (it!=ss.end()&&it!=ss.begin());
}
bool hasnext(set<line>::iterator it)
{
return (it!=ss.end()&&next(it)!=ss.end());
}
double intersect(line a,line b)
{
if(a.m==b.m)
return (1LL<<50);
return (1.0*(a.c-b.c))/(b.m-a.m);
}
bool isbad(line a,line b,line c)
{
return intersect(b,c)<intersect(b,a);
}
bool isbad(set<line>::iterator it)
{
return hasnext(it)&&hasprev(it)&&isbad(*prev(it),*it,*next(it));
}
set<line>::iterator update(set<line>::iterator it)
{
double x=(hasnext(it)?intersect(*it,*next(it)):(1LL<<50));
line cur=*it;
cur.x=x;
ss.erase(it);
it=ss.insert(cur).first;
return it;
}
void addline(long long m,long long c,int ind)
{
set<line>::iterator it=ss.insert({m,c,ind}).first;
if(isbad(it))
{
ss.erase(it);
return;
}
while(hasnext(it)&&isbad(next(it))) ss.erase(next(it));
while(hasprev(it)&&isbad(prev(it))) ss.erase(prev(it));
it=update(it);
if(hasnext(it)) update(next(it));
if(hasprev(it)) update(prev(it));
}
pair<long long,int> query(long long x)
{
line q;
q.x=x; q.isq=1;
set<line>::iterator it=ss.lower_bound(q);
if(it==ss.end())
return {(1LL<<50),-1};
return {((*it).m)*x+((*it).c),(*it).ind};
}
};
convex_hull ss[2];
int n,k;
int arr[100005];
long long sum[100005];
long long mem[201][100005];
int sp[201][100005];
int main()
{
int st=1,t=1;
//scanf("%d %d",&st,&t);
while(t--)
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
sum[i]=arr[i];
sum[i]+=sum[i-1];
}
for(int i=0;i<=k;i++)
{
mem[i][n+1]=0;
}
ss[0].ss.clear(); ss[1].ss.clear();
for(int j=k;j>=0;j--)
{
for(int i=n;i>=j+1;i--)
{
mem[j][i]=mem[j][i+1];
if(j==k)
{
ss[j%2].addline(sum[i-1],mem[j][i],i);
sp[j][i]=n+1;
continue;
}
/*for(int l=i+1;l<=n+1;l++)
{
mem[i][j]=max(mem[i][j],(sum[l-1]-sum[i-1])*(sum[i-1])+mem[l][j+1]);
mem[i][j]=sum[l-1]*sum[i-1]-sum[i-1]*sum[i-1]+mem[l][j+1];
}*/
pair<long long,int> x=ss[1-j%2].query(sum[i-1]);
mem[j][i]=max(mem[j][i],x.first-sum[i-1]*sum[i-1]);
sp[j][i]=x.second;
//cout << i << " " << j << " " << mem[i][j] << query(j+1,sum[i-1]) << endl;
ss[j%2].addline(sum[i-1],mem[j][i],i);
}
ss[1-j%2].ss.clear();
ss[j%2].addline(sum[n],0,n+1);
}
cout << mem[0][1] << endl;
int x=1;
for(int i=0;i<k;i++)
{
cout << sp[i][x]-1 << " \n"[i==k-1];
x=sp[i][x];
//for(int j=1;j<=n;j++)
// cout << sp[i][j] << " \n"[j==n];
}
}
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 376 KB | Integer 7 violates the range [1, 6] |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 376 KB | Integer 50 violates the range [1, 49] |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 2 ms | 376 KB | Integer 200 violates the range [1, 199] |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 504 KB | Integer 1000 violates the range [1, 999] |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 19 ms | 2168 KB | Integer 10000 violates the range [1, 9999] |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 276 ms | 18780 KB | Integer 100000 violates the range [1, 99999] |
| 2 | Halted | 0 ms | 0 KB | - |