oj.uz

Submission #475249

# Submission time Handle Problem Language Result Execution time Memory
475249 2021-09-21T15:51:50 Z Dymo Candies (JOI18_candies) C++14
100 / 100
 915 ms 15960 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Output is correct
2 Correct 8 ms 460 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 8 ms 460 KB Output is correct
5 Correct 9 ms 460 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 8 ms 460 KB Output is correct
8 Correct 8 ms 432 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 9 ms 424 KB Output is correct
11 Correct 8 ms 460 KB Output is correct
12 Correct 10 ms 460 KB Output is correct
13 Correct 10 ms 556 KB Output is correct
14 Correct 8 ms 452 KB Output is correct
15 Correct 11 ms 460 KB Output is correct
16 Correct 10 ms 460 KB Output is correct
17 Correct 9 ms 460 KB Output is correct
18 Correct 9 ms 460 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 8 ms 460 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 460 KB Output is correct
2 Correct 8 ms 460 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 8 ms 460 KB Output is correct
5 Correct 9 ms 460 KB Output is correct
6 Correct 8 ms 460 KB Output is correct
7 Correct 8 ms 460 KB Output is correct
8 Correct 8 ms 432 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 9 ms 424 KB Output is correct
11 Correct 8 ms 460 KB Output is correct
12 Correct 10 ms 460 KB Output is correct
13 Correct 10 ms 556 KB Output is correct
14 Correct 8 ms 452 KB Output is correct
15 Correct 11 ms 460 KB Output is correct
16 Correct 10 ms 460 KB Output is correct
17 Correct 9 ms 460 KB Output is correct
18 Correct 9 ms 460 KB Output is correct
19 Correct 8 ms 460 KB Output is correct
20 Correct 8 ms 460 KB Output is correct
21 Correct 905 ms 15844 KB Output is correct
22 Correct 897 ms 15696 KB Output is correct
23 Correct 903 ms 15704 KB Output is correct
24 Correct 900 ms 15540 KB Output is correct
25 Correct 907 ms 15504 KB Output is correct
26 Correct 911 ms 15544 KB Output is correct
27 Correct 902 ms 15728 KB Output is correct
28 Correct 902 ms 15680 KB Output is correct
29 Correct 896 ms 15680 KB Output is correct
30 Correct 892 ms 15740 KB Output is correct
31 Correct 883 ms 15740 KB Output is correct
32 Correct 910 ms 15960 KB Output is correct
33 Correct 915 ms 15676 KB Output is correct
34 Correct 909 ms 15556 KB Output is correct
35 Correct 899 ms 15544 KB Output is correct
36 Correct 905 ms 15452 KB Output is correct
37 Correct 890 ms 15272 KB Output is correct
38 Correct 904 ms 15324 KB Output is correct
39 Correct 881 ms 15180 KB Output is correct
40 Correct 889 ms 15188 KB Output is correct
41 Correct 896 ms 15200 KB Output is correct
42 Correct 893 ms 15324 KB Output is correct
43 Correct 888 ms 15400 KB Output is correct
44 Correct 905 ms 15400 KB Output is correct
45 Correct 913 ms 15456 KB Output is correct
46 Correct 902 ms 15468 KB Output is correct
47 Correct 904 ms 15468 KB Output is correct
48 Correct 907 ms 15264 KB Output is correct
49 Correct 886 ms 15208 KB Output is correct
50 Correct 899 ms 15240 KB Output is correct