Submission #655282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
655282	2022-11-03T17:44:52 Z	benjaminkleyn	Split the sequence (APIO14_sequence)	C++17	11 / 100	81 ms	131072 KB

sequence

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
     
    struct Line {
    	mutable ll k, m, p, idx;
    	bool operator<(const Line& o) const { return k < o.k; }
    	bool operator<(ll x) const { return p < x; }
    };
     
    struct LineContainer : multiset<Line, less<>> {
    	static const ll inf = LLONG_MAX;
    	ll div(ll a, ll b) {
    		return a / b - ((a ^ b) < 0 && a % b); }
    	bool isect(iterator x, iterator y) {
    		if (y == end()) return x->p = inf, 0;
    		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
    		else x->p = div(y->m - x->m, x->k - y->k);
    		return x->p >= y->p;
    	}
    	void add(ll k, ll m, int idx) {
    		auto z = insert({k, m, 0, idx}), 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));
    	}
    	pair<ll,int> query(ll x) {
    		assert(!empty());
    		auto l = lower_bound(x);

    		pair<ll,int> res = {l->k * x + l->m, l->idx};

            while (l != begin())
                l = prev(erase(prev(l)));

            return res;
    	}
    };
     
    int N, K, a[100001];
    ll pref[100001] = {0};
    ll dp[100001][201] = {0};
    int last_split[100001][201];
     
    int main()
    {
        cin >> N >> K;
        for (int i = 1; i <= N; i++)
        {
             cin >> a[i];
             pref[i] = pref[i-1] + a[i];
        }
     
        LineContainer cht;
        for (int k = 1; k <= K; k++)
        {
            cht.clear();
            for (int i = k + 1; i <= N; i++)
            {
                dp[i][k] = 0;
                cht.add(pref[i-1], dp[i-1][k-1] - pref[i-1] * pref[i-1], i-1);
                auto [val, idx] = cht.query(pref[i]);
                dp[i][k] = val;
                last_split[i][k] = idx;
            }
        }
     
        cout << dp[N][K] << '\n';
     
        int i = N;
        do
        {
            i = last_split[i][K];
            cout << i << ' ';
        } while (--K);
        cout << '\n';
     
        return 0;
    }

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	1 ms	724 KB	contestant found the optimal answer: 311760000 == 311760000
3	Correct	2 ms	724 KB	contestant found the optimal answer: 1989216017013 == 1989216017013
4	Incorrect	1 ms	724 KB	contestant didn't find the optimal answer: 1492939812514 < 1499437552673
5	Halted	0 ms	0 KB	-