Submission #331600

#	Time	Username	Problem	Language	Result	Execution time	Memory
331600		limabeans	Money (IZhO17_money)	C++17	9 / 100	1595 ms	384 KiB

money

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;



bool test(int mask, vector<int> a) {
    int n = a.size();
    vector<int> w = {-1};
    for (int i=0; i<n-1; i++) {
	if (mask>>i&1) {
	    w.push_back(i);
	}
    }

    w.push_back(n-1);

    vector<vector<int>> v;
    for (int i=1; i<(int)w.size(); i++) {
	vector<int> tmp;
	for (int j=w[i-1]+1; j<=w[i]; j++) {
	    tmp.push_back(a[j]);
	}
	v.push_back(tmp);
    }


    // for (auto p: v) {
    // 	for (int x: p) cout<<x<<" ";
    // 	cout<<" | ";
    // }
    // cout<<endl;

    vector<int> res;

    for (auto p: v) {
	vector<int> nxt;

	bool done = false;
	for (int i=0; i<(int)res.size(); i++) {
	    if (done || res[i] <= p[0]) {
		nxt.push_back(res[i]);
	    } else {
		nxt.insert(nxt.end(), p.begin(), p.end());
		nxt.push_back(res[i]);
		done = true;
	    }
	}

	if (!done) {
	    nxt.insert(nxt.end(), p.begin(), p.end());
	}


	res = nxt;

	// watch(res.size());
	// for (int x: res) cout<<x<<" ";
	// cout<<endl;
	
    }


    // for (int x: res) cout<<x<<" ";
    // cout<<endl;

    assert((int)res.size() == n);

    bool ok = true;

    for (int i=1; i<n; i++) {
	ok &= (res[i]>=res[i-1]);
    }

    return ok;
}



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }



    int ans = n;

    for (int mask=0; mask<(1<<(n-1)); mask++) {
	if (test(mask, a)) {
	    ans = min(ans, 1+__builtin_popcount(mask));
	}
    }


    cout<<ans<<endl;    
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55