oj.uz

Submission #272847

# Submission time Handle Problem Language Result Execution time Memory
272847 2020-08-18T16:14:42 Z anubhavdhar Split the sequence (APIO14_sequence) C++14
71 / 100
 462 ms 131076 KB 
#include<bits/stdc++.h>
 
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
 
using namespace std;
 
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
 
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
 
ll dp[MAXN][201], pre[MAXN], par[MAXN][201];
int N, K;
 
struct line //mx + c
{
	mutable ll m, c, p, ind;
	bool operator < (const line& o) const {return m < o.m;}
	bool operator < (ll x) const {return p < x;}
};
 
struct CHT_black_box : multiset<line, less<>>
{
	int mode;
	CHT_black_box(){mode = 1;}
	void set_mode(string S) {mode = (S[1] == 'i' || S[1] == 'I') ? -1 : 1;}
	ll div(ll a, ll b) {return a/b - ((a^b) < 0 && a%b);}
	bool isect(iterator x, iterator y)
	{
		if(y == end()){x->p = INF; return false;}
		if(x->m == y->m)	x->p = (x->c > y->c) ? INF : -INF;
		else	x->p = div((y->c - x->c),(x->m - y->m));
		return (x->p >= y->p);
	}
	void add(ll slope, ll intercept, ll id)
	{
		auto z = insert({mode * slope, mode * intercept, 0, id}), y = z++, x = y;
		while(isect(y, z))	z = erase(z);
		if(x != begin() && isect(--x, y))	isect(x, y = erase(y));
		while((y=x) != begin() && (--x)->p >= y->p)	isect(x, erase(y));
	}
	pll query(ll x)
	{
		assert(!empty());
		auto l = *lower_bound(x);
		return mp (mode * (l.m * x + l.c), l.ind);
	}
}box[1];
 
signed main()
{
 
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
 
	ll p, q = INF;
	cin>>N>>K;
	pre[0] = 0;
	F0Re(i, N)
		cin>>p, pre[i] = p + pre[i-1];
 
	p = 0;
 
	// F0Re(i, N)
	// 	cout<<pre[i]<<' ';
	// cout<<endl;
 
	F0R(i, N+1)
		F0R(j, K+1)
			dp[i][j] = par[i][j] = 0;
 
	// F0Rr(k, j-1, i) dp[i][j] = max(dp[k][j-1] + pre[N]*pre[i] - pre[i]*pre[i] - pre[N]*pre[k] + pre[i]*pre[k]), dp[i][j]);
 
	F0Re(j, K)
	{
      	box[0].clear();
      	if(j > 1)	box[0].add(pre[j-1], dp[j-1][j-1] - pre[j-1] * pre[N], j-1);
		F0Rr(i, j, N+1)
		{
			if(j == 1)
				dp[i][j] = pre[i]*(pre[N] - pre[i]);
			else {pll v = box[0].query(pre[i]); dp[i][j] = pre[N]*pre[i] - pre[i]*pre[i] + v.ff; par[i][j] = v.ss;}
			// p = max(p, dp[i][j]);
			if(j == K) p = max(p, dp[i][j]);
       		if(j > 1) box[0].add(pre[i], dp[i][j-1] - pre[i] * pre[N], i);
        }
	}
 
 
	cout<<p<<'\n';
 
	F0Re(i, N)
		if(dp[i][K] == p)
		{
			q = i; break;
		}
 
	while(q and K)
	{
		cout<<q<<' ';
		q = par[q][K--];
	}
 
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 384 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 384 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 384 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 384 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 1 ms 384 KB contestant found the optimal answer: 1 == 1
7 Correct 1 ms 384 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 384 KB contestant found the optimal answer: 1 == 1
9 Correct 0 ms 384 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 1 ms 384 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 384 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 384 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 1 ms 416 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 384 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 0 ms 384 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 384 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 384 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 512 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 1 ms 512 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 512 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 1 ms 512 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 0 ms 512 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 512 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 1 ms 512 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 512 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 1 ms 512 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 1044 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 3 ms 1024 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 1024 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 4 ms 1024 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 3 ms 1024 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 3 ms 1024 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 2 ms 896 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 2 ms 1024 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 2 ms 1024 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3584 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 2 ms 3584 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 28 ms 3584 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 3 ms 3584 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 29 ms 3584 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 24 ms 3584 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 29 ms 3584 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 28 ms 3584 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 8 ms 3584 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 15 ms 3584 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32512 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 19 ms 32512 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 462 ms 32760 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 22 ms 32768 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 260 ms 32632 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 272 ms 32584 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 312 ms 32640 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 270 ms 32632 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 283 ms 32640 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 374 ms 32664 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -