Submission #881158

#	Time	Username	Problem	Language	Result	Execution time	Memory
881158		cpptowin	Split the sequence (APIO14_sequence)	C++17	71 / 100	46 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf 1000000000
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
using namespace std;
int n, k;
int a[maxn];
int pre[maxn];
int sum(int l, int r)
{
    return pre[r] - pre[l - 1];
}
namespace sub1
{
    int solve(int l, int r, int k, vi &v)
    {
        if (k > r - l + 1)
            return 0;
        if (k == 0 or l == r)
            return 0;
        int ans = 0;
        vi cc;
        int pos = l, sl = 0;
        fo(i, l, r - 1)
        {
            fo(j, 0, k - 1)
            {
                int val = solve(l, i, j, cc) + solve(i + 1, r, k - j - 1, cc) + sum(l, i) * sum(i + 1, r);
                if (ans < val)
                {
                    ans = val;
                    pos = i;
                    sl = j;
                }
            }
        }
        v.pb(pos);
        solve(l, pos, sl, v);
        solve(pos + 1, r, k - sl - 1, v);
        return ans;
    }
}
struct CHT
{
    vector<pair<int,pii>> line;
    int pos = 0;
    void clear()
    {
        line.clear();
        pos = 0;
    }
    int eval(pii a, int x)
    {
        return a.fi * x + a.se;
    }
    bool bad(pii a, pii b, pii c)
    {
        return (double)(b.se - a.se) / (a.fi - b.fi) <= (double)(c.se - a.se) / (a.fi - c.fi);
    }
    void add(pair<int,pii> newline)
    {
        line.pb(newline);
        while (line.size() > 2 && bad(line[line.size() - 3].se, line[line.size() - 2].se, line.back().se))
            line.erase(line.end() - 2);
    }
    pii get(int x)
    {
        if (pos >= line.size())
            pos = line.size() - 1;
        while (pos < line.size() - 1 && eval(line[pos].se, x) <= eval(line[pos + 1].se, x))
            pos++;
        return make_pair(eval(line[pos].se, x),line[pos].fi);
    }
};
namespace full
{
    CHT cht;
    int dp[100010][2];
    int trace[100010][200];
    void solve()
    {
        // fo(i, 0, k) cht[i].add({0, 0});
        fo(j, 1, k)
        {
            cht.clear();
            cht.add({0,{0, 0}});
            fo(i, 1, n)
            {
                pii now = cht.get(pre[n] - pre[i]);
                dp[i][j % 2] = now.fi + pre[i] * (pre[n] - pre[i]);
                if(j - 1 > 0)
                trace[i][j] = now.se;
                cht.add({i,{-pre[i], dp[i][1 - j % 2]}});
            }
        }
        int pos = 0,res = 0;
        fo(i,k,n) if(res < dp[i][k % 2])
        {
            pos = i;
            res = dp[i][k % 2];
        }
        if(res == 0)
        {
            cout << res << "\n";
            fo(i,1,k) cout << i << ' ' ;
            return ;
        }
        cout << res;en;
        vi ans;
        int j = k,id;
        ans.pb(pos);
        fo(i,1,k - 1)
        {
            pos = trace[pos][j--];
            ans.pb(pos);
        }
        reverse(ans.begin(),ans.end());
        for(int it : ans) cout << it << ' ';
    }
}
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    fo(i, 1, n)
    {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    // if (n <= 10)
    // {
    //     vi v;
    //     cout << sub1::solve(1, n, k, v);
    //     en;
    //     sort(v.begin(), v.end());
    //     for (int it : v)
    //         cout << it << ' ';
    // }
    // else
    full::solve();
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<long long int, long long int> CHT::get(long long int)':
sequence.cpp:82:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         if (pos >= line.size())
      |             ~~~~^~~~~~~~~~~~~~
sequence.cpp:84:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         while (pos < line.size() - 1 && eval(line[pos].se, x) <= eval(line[pos + 1].se, x))
      |                ~~~~^~~~~~~~~~~~~~~~~
sequence.cpp: In function 'void full::solve()':
sequence.cpp:124:19: warning: unused variable 'id' [-Wunused-variable]
  124 |         int j = k,id;
      |                   ^~
sequence.cpp: At global scope:
sequence.cpp:135:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  135 | main()
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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