oj.uz

Submission #465303

# Submission time Handle Problem Language Result Execution time Memory
465303 2021-08-15T14:26:43 Z arnob918 Split the sequence (APIO14_sequence) C++14
0 / 100
 35 ms 3868 KB 
#include    <bits/stdc++.h>
#include    <stdio.h>
#include    <ext/pb_ds/assoc_container.hpp>// For pbds.Don't use tree as variable name.
#include    <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb          push_back
#define eb          emplace_back
#define mem(x,i)    memset(x,i,sizeof(x))
#define ff          first
#define ss          second
#define all(x)      x.begin(),x.end()
#define Q 			int t; scanf("%d", &t); for(int q=1; q<=t; q++)

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;//%Lf
typedef pair<ll, ll> pi;

template <typename T>  using orderedSet = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
    //order_of_key(k) - number of element strictly less than k.
    //find_by_order(k) - k'th element in set.(0 indexed)(iterator)

                            /* Debug Tools */
#define error(args...) \
{ \
    string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
    stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);\
}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr<< *it << " = " << a <<",\n"[++it==istream_iterator<string>()];
    err(it, args...);
}

const int MOD = 1e9+7 ; //For big mod
template<typename T>inline T gcd(T a, T b){T c;while (b){c = b;b = a % b;a = c;}return a;} // better than __gcd
ll powmod(ll a,ll b){ll res=1;a%=MOD;if(b<0) return 0;for(; b; b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}

const int xx[] = {+1, -1, +0, +0};//, +1, +1, -1, -1};// exclude last four when side adjacent
const int yy[] = {+0, +0, +1, -1};//, +1, -1, +1, -1};
const int INF    = 0x3f3f3f3f;// useful for memset
const ll LL_INF  = 0x3f3f3f3f3f3f3f3f;
const double PI  = acos(-1.0);
const double eps = 1e-9;
const int mxn     = 1e5+5; //CHECK here for every problem
const int mod    = 1e9+7;

int n, k;
vector<pi> v;
ll a[mxn];
ll z[mxn];

pi mid(int b, int e){
	int lo = b;
	int hi = e;
	int pos = lo;
	while(hi >= lo){
		int m1 = lo+(hi-lo)/3;
		int m2 = hi-(hi-lo)/3;
		ll c1 = abs((a[m1]-(b==0? 0: a[b-1])) - (a[e]-a[m1]));
		ll c2 = abs((a[m2]-(b==0? 0: a[b-1])) - (a[e]-a[m2]));
		if(c2 > c1){
			pos = m1;
			hi = m2-1;
		}
		else{
			pos = m2;
			lo = m1+1;
		}
	}
	pi ret;
	ret.ff = (a[pos]-(b==0? 0: a[b-1])) * (a[e]-a[pos]);
	ret.ss = pos+1;
	return ret;
}

void call(int b=0, int e=n-1){
	if(b==e) return;
	//error(b, e);
	pi val = mid(b, e);
	//error(val.ff, val.ss);
	v.pb(val);
	call(b, val.ss-1);
	call(val.ss, e);
}

int main()
{
	cin >> n >> k;
	
	for(int i=0; i<n;i++){
		cin >> a[i];
		if(a[i] == 0){
			z[i]++;
			i--;
			n--;
		}
	}
	for(int i=1; i<n; i++) a[i] += a[i-1];
	for(int i=1; i<n; i++) z[i] += z[i-1];
	call();
	sort(all(v), greater<pi>());
	ll ans = 0;
	for(int i=0; i<k; i++){
		ans += v[i].ff;
	}
	cout << ans << '\n';
	for(int i=0; i<k; i++){
		printf("%lld ", v[i].ss+z[v[i].ss]);
	}
	printf("\n");
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB contestant found the optimal answer: 108 == 108
2 Incorrect 1 ms 204 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB contestant didn't find the optimal answer: 1093726 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 204 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 204 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 204 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 1 ms 204 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Incorrect 1 ms 204 KB Integer 0 violates the range [1, 199]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB contestant didn't find the optimal answer: 21419072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 588 KB contestant didn't find the optimal answer: 1794250000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3868 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Incorrect 35 ms 3812 KB contestant didn't find the optimal answer: 19874432171 < 19874432173
3 Halted 0 ms 0 KB -