Submission #1313324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313324		wedonttalkanymore	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	332 KiB

sequence

#include <bits/stdc++.h>
/*
    Checklist: 
    - Check statement: 
    - Check filename: 
    - Check test limit: 
    - Stresstest: 
*/
using namespace std;
using ll = long long;

//#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n, k;
int a[N];
ll pfs[N];

struct Convexhull {
    vector <pair <pii, int> > hull;
    void reset() {
        hull.clear();
    }
    ll cal(pii a, ll x) {
        return a.fi * x + a.se;
    }
    bool bad(pii x, pii y, pii z) {
        return (y.se - x.se) * (y.fi - z.fi) <= (z.se - y.se) * (x.fi - y.fi);
    }
    void add(ll a, ll b, ll id) {
        if (hull.size() < 2) {
            hull.push_back({{a, b}, id});
            return;
        }
        int sz = hull.size();
        while(sz >= 2 && bad(hull[sz - 2].fi, hull[sz - 1].fi, make_pair(a, b))) {
//        	cout << "tt: " << hull[sz - 1].fi.fi << ' ' << hull[sz - 1].fi.se << '\n';
            hull.pop_back();
            sz--;
        }
        hull.push_back({{a, b}, id});
    }
    ll get(ll x) {
        int l = 0, r = hull.size() - 1, ans = 0;
//        if (l == 0 && r == -1) {
//        	cout << "gg: " << '\n';
////        	return 0;
//		}
        while(l <= r) {
            int mid = (l + r) / 2;
            if (mid + 1 == hull.size()) {
                ans = mid;
                break;
            }
            if (cal(hull[mid].fi, x) <= cal(hull[mid + 1].fi, x)) {
                ans = mid + 1;
                l = mid + 1;
            }
            else {
                ans = mid;
                r = mid - 1;
            }
        }
//        if (l == 0 && r == -1) {
//        	cout << "gg: " << '\n';
////        	return 0;
//		}
        if (x == 4) {
//            for (auto tt : hull) {
//            	cout << "at: " << tt.fi.fi << ' ' << tt.fi.se << ' ' << tt.se << ' ';
//            	cout << cal(tt.fi, x) << '\n';
//			}
        }
        if (ans < hull.size()) return hull[ans].se;
        return 0;
    }
} cht;

ll dp[N][2];
int trace[205][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) pfs[i] = pfs[i - 1] + a[i];
    for (int i = 1; i <= n; i++) dp[i][0] = pfs[i] * (pfs[n] - pfs[i]);
    for (int i = 2; i <= k; i++) {
        cht.reset();
        for (int j = 1; j <= n; j++) {
            int idx = cht.get(pfs[n] - pfs[j]);
            dp[j][1] = dp[idx][0] - pfs[idx] * (pfs[n] - pfs[j]) + pfs[j] * (pfs[n] - pfs[j]);
            trace[i][j] = idx;
//            cout << i << ' ' << j << ' ' << idx << '\n';
            cht.add(-pfs[j], dp[j][0], j);
        }
        for (int j = 1; j <= n; j++) dp[j][0] = dp[j][1];
//        for (int j = 1; j <= n; j++) cout << dp[j][0] << ' '; cout << '\n';
    }
//    cout << dp[n][0] << '\n';
	ll ans = 0, idx = n;
    for (int i = 1; i <= n; i++) {
    	if (ans < dp[i][0]) {
    		ans = dp[i][0];
    		idx = i;
		}
	}
    vector <ll> res;
    int cur = idx;
    for (int i = k; i >= 1; i--) {
        res.push_back(cur);
        cur = trace[i][cur];
    }
    reverse(res.begin(), res.end());
    cout << ans << '\n';
    for (auto x : res) cout << x << ' ';
    return 0;
}
/*
5 3
2 1 4 1 5 
*/

Compilation message (stderr)

sequence.cpp: In member function 'void Convexhull::add(ll, ll, ll)':
sequence.cpp:36:37: warning: narrowing conversion of 'id' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   36 |             hull.push_back({{a, b}, id});
      |                                     ^~
sequence.cpp:45:33: warning: narrowing conversion of 'id' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   45 |         hull.push_back({{a, b}, id});
      |                                 ^~
sequence.cpp: In function 'int main()':
sequence.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sequence.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29