oj.uz

Submission #465307

# Submission time Handle Problem Language Result Execution time Memory
465307 2021-08-15T14:36:19 Z arnob918 Split the sequence (APIO14_sequence) C++14
0 / 100
 19 ms 1988 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];
	}
	for(int i=1; i<n; i++) a[i] += a[i-1];
	int ans = 0;
	vector<int> aa;
	for(int msk = 0; msk<(1<<n); msk++){
		if(__builtin_popcount(msk) != k)continue;
		int la = -1;
		int cnt = 0;
		vector<int> xx;
		for(int i=0; i<n; i++){
			if(msk&(1<<i)){
				if(la == -1){
					cnt += a[i]*(a[n-1]-a[i]);
					la = i;
				}
				else{
					cnt += (a[i]-a[la])*(a[n-1]-a[i]);
					la = i;
				}
				xx.pb(i+1);
			}
		}
		if(cnt > ans){
			ans = cnt;
			aa = xx;
		}
	}
			
	
	cout << ans << '\n';
	for(int i=0; i<k; i++){
		printf("%d ", aa[i]);
	}
	printf("\n");
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 204 KB contestant found the optimal answer: 999 == 999
3 Runtime error 1 ms 332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB declared answer doesn't correspond to the split scheme: declared = 1094706, real = 413262
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB declared answer doesn't correspond to the split scheme: declared = 613673465, real = 484112
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB declared answer doesn't correspond to the split scheme: declared = 22138012, real = 275952
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 332 KB declared answer doesn't correspond to the split scheme: declared = 2090982627, real = 1606920
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 1988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -