Submission #589921

#	Time	Username	Problem	Language	Result	Execution time	Memory
589921		yutabi	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	675 ms	283472 KiB

boxes

#include "boxes.h"


#include <bits/stdc++.h>
using namespace std;


#define pb push_back


typedef long long ll;



long long delivery(int N, int K, int L, int p[])
{
    vector <ll> l_cost(K);
    vector <ll> r_cost(K);


    vector <ll> l_final;
    vector <ll> r_final;


    vector <ll> l;
    vector <ll> m;
    vector <ll> r;


    for(int i=0;i<N;i++)
    {
        if(p[i]*2<L)
        {
            l.pb(p[i]);
        }

        if(p[i]*2==L)
        {
            m.pb(p[i]);
        }

        if(p[i]*2>L)
        {
            r.pb(L-p[i]);
        }
    }

    reverse(r.begin(),r.end());

    l_final.pb(0);
    r_final.pb(0);


    for(int i=0;i<l.size();i++)
    {
        ll sz=l_final.size();
        sz%=K;

        l_cost[sz]+=l[i];
        l_cost[sz]+=l[i];
        
        l_final.pb(l_cost[sz]);
    }
    

    for(int i=0;i<r.size();i++)
    {
        ll sz=r_final.size();
        sz%=K;

        r_cost[sz]+=r[i];
        r_cost[sz]+=r[i];
        
        r_final.pb(r_cost[sz]);
    }
    

    for(int i=0;i<m.size();i++)
    {
        ll sz=l_final.size();
        sz%=K;

        l_cost[sz]+=m[i];
        l_cost[sz]+=m[i];
        
        l_final.pb(l_cost[sz]);


        sz=r_final.size();
        sz%=K;

        r_cost[sz]+=m[i];
        r_cost[sz]+=m[i];
        
        r_final.pb(r_cost[sz]);
    }

    /*for(int i=0;i<l_final.size();i++)
    {
        printf("%lld\n",l_final[i]);
    }

    printf("\n");

    for(int i=0;i<r_final.size();i++)
    {
        printf("%lld\n",r_final[i]);
    }*/

    ll ans=-1;

    for(int i=0;i<l_final.size();i++)
    {
        if(N-i>=r_final.size())
        {
            continue;
        }

        ll res=l_final[i]+r_final[N-i];

        if(res<ans || ans==-1)
        {
            ans=res;
        }
    }

    for(int i=0;i<l_final.size();i++)
    {
        if(N-i-K>=r_final.size())
        {
            continue;
        }

        ll res=l_final[i]+r_final[N-i-K]+L;

        if(res<ans || ans==-1)
        {
            ans=res;
        }
    }


    return ans;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i=0;i<l.size();i++)
      |                 ~^~~~~~~~~
boxes.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i=0;i<r.size();i++)
      |                 ~^~~~~~~~~
boxes.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<m.size();i++)
      |                 ~^~~~~~~~~
boxes.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for(int i=0;i<l_final.size();i++)
      |                 ~^~~~~~~~~~~~~~~
boxes.cpp:114:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         if(N-i>=r_final.size())
      |            ~~~^~~~~~~~~~~~~~~~
boxes.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=0;i<l_final.size();i++)
      |                 ~^~~~~~~~~~~~~~~
boxes.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         if(N-i-K>=r_final.size())
      |            ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30