Submission #475249

#	Time	Username	Problem	Language	Result	Execution time	Memory
475249		Dymo	Candies (JOI18_candies)	C++14	100 / 100	915 ms	15960 KiB

candies

#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define ull unsigned ll
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937_64 rnd;
const ll maxn=7e5+100;
const ll mod =1e9+7   ;
const ll base=1e18;
const ld eps=1e-7;
/// goal 1/7
/// you will be the best but now you just are trash
ll b[maxn];
ll a[maxn];

vector<ll> mer(vector<ll> vt,vector<ll> vt1)
{
    vector<ll> ans(vt.size()+vt1.size()-1,-base);
    ll i=0;
    ll j=0;
    while (i+j<ans.size())
    {
        ans[i+j]=max(ans[i+j],vt[i]+vt1[j]);
        if (i==vt.size()-1)
            j++;
        else if (j==vt1.size()-1)
            i++;
        else
        {
            if (vt[i+1]+vt1[j]>vt[i]+vt1[j+1])
                i++;
            else
                j++;
        }
    }
    return ans;
}
vector<ll> mer1(vector<ll> vt, vector<ll> vt1)
{
    ll h=max((ll)vt.size(),(ll)vt1.size());
    vector<ll> vtp(h,-base);
    for (int i=0; i<vtp.size(); i++)
    {
        if(i<vt.size())
            vtp[i]=max(vtp[i],vt[i]);
        if (i<vt1.size())
            vtp[i]=max(vtp[i],vt1[i]);
    }
    return vtp;
}
vector<vector<ll>> dosth(ll left,ll right)
{
    vector<vector<ll>> ans;
    if (left==right)
    {

        for (int t=0; t<=3; t++)
        {
            if (t==0)
            {
                vector<ll> vt(1,0);
                ans.pb(vt);
            }
            else if (t==1||t==2)
            {
                vector<ll> vt(1,-base);
                ans.pb(vt);
            }
            else
            {
                vector<ll> vt(2,0);
                vt[1]=b[left];
                ans.pb(vt);
            }
        }
        return ans;
    }
    ll mid=(left+right)/2;
    auto p=dosth(left,mid);
    auto p1=dosth(mid+1,right);
    for (int t=0; t<=3; t++)
    {
        vector<ll> vt;
        for (int h=0; h<=2; h++)
        {
            ll lf=0;
            ll rt=0;
            if (t&(1ll<<1))
                lf+=2;
            if (h&(1ll<<1))
                lf+=1;
            if (t&(1ll<<0))
                rt+=1;
            if (h&(1ll<<0))
                rt+=2;
            auto op=mer(p[lf],p1[rt]);
           /* if (left==1&&right==2&&t==0&&lf==1&&rt==0)
            {
                cout <<lf<<" "<<rt<<" chk"<<endl;
                for (auto to:p1[rt])
                {
                    cout <<to<<" ";
                }
                cout <<endl;
                for(auto to:op)
                {
                    cout <<to<<" ";
                }
                cout <<endl;
            }*/
            vt=mer1(vt,op);
        }

        ans.pb(vt);
    }

    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin>>n ;
    for (int i=1; i<=n; i++)
    {
        cin>>b[i];
    }
    vector<vector<ll>> ans= dosth(1,n);
    vector<ll> vt;
    for (int t=0;t<4;t++) vt=mer1(vt,ans[t]);
    for (int t=1;t<=(n+1)/2;t++) cout <<vt[t]<<endl;
}

Compilation message (stderr)

candies.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("unroll-loops, no-stack-protector")
      | 
candies.cpp: In function 'std::vector<long long int> mer(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:31:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while (i+j<ans.size())
      |            ~~~^~~~~~~~~~~
candies.cpp:34:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (i==vt.size()-1)
      |             ~^~~~~~~~~~~~~
candies.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         else if (j==vt1.size()-1)
      |                  ~^~~~~~~~~~~~~~
candies.cpp: In function 'std::vector<long long int> mer1(std::vector<long long int>, std::vector<long long int>)':
candies.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i=0; i<vtp.size(); i++)
      |                   ~^~~~~~~~~~~
candies.cpp:54:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(i<vt.size())
      |            ~^~~~~~~~~~
candies.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (i<vt1.size())
      |             ~^~~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:137:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92