Submission #881163

#	Time	Username	Problem	Language	Result	Execution time	Memory
881163		cpptowin	Split the sequence (APIO14_sequence)	C++17	100 / 100	571 ms	84944 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 100010
#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<long long, long long>
#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];
long long pre[maxn];
long long sum(int l, int r)
{
    return pre[r] - pre[l - 1];
}
struct CHT
{
    vector<pair<int,pii>> line;
    int pos = 0;
    void clear()
    {
        line.clear();
        pos = 0;
    }
    long long 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(long long 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;
    long long dp[100010][2];
    int trace[100010][200];
    void solve()
    {
        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;
        long long 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];
    }
    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:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if (pos >= line.size())
      |             ~~~~^~~~~~~~~~~~~~
sequence.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         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:94:19: warning: unused variable 'id' [-Wunused-variable]
   94 |         int j = k,id;
      |                   ^~
sequence.cpp: At global scope:
sequence.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main()
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         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: 29 / 29