Submission #780231

#	Time	Username	Problem	Language	Result	Execution time	Memory
780231		vjudge1	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	113 ms	71040 KiB

boxes

#include "boxes.h"
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;


void f(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

long long int  calc(int k, int l, vector<array<long long int, 2>> s, vector<array<long long int, 2>> t){
    long long  int ans = 0;

    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());

    long long  int p=0;  


    for(int i=0; i<s.size(); i++){
        long long int f=min(p, s[i][1]);
        p-=f;
        s[i][1]-=f;

        ans+=(s[i][1]+k-1)/k*s[i][0];
        p+=((s[i][1]+k-1)/k)*k;
        f=min(p, s[i][1]);


        p-=f;
        s[i][1]-=f;    
    }

    p=0;
    for(int i=0; i<t.size(); i++){
        long long int f=min(p, t[i][1]);
        p-=f;
        t[i][1]-=f;
        ans+=(t[i][1]+k-1)/k*(l-t[i][0]);
        p+=((t[i][1]+k-1)/k)*k;
        f=min(p, t[i][1]);
        p-=f;
        t[i][1]-=f;
    }


    return ans*2;


}

long long int  d(int n, int k, int l, vector<array<long long int, 2>> a){  
    if(!a.size()) return 0;

    if(l%2==0){
       int n=a.size();
       vector<array<long long int, 2>> s, t;
        for(int i=0; i<n; i++){
            if(a[i][0]<=l/2) s.push_back(a[i]);
            else t.push_back(a[i]); 
        }
        long long int sum=0;


        for(auto i: s){
            sum+=i[1];
        }

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

        long long int ans=1e18;
        ans=calc(k, l, s, t);

         if(sum%k){
            long long int f=sum%k;
            long long int pf=k-f;

            swap(f, pf);

            for(int i = s.size()-1; i>=0; i--){
               int pff=min(pf, s[i][1]);
                s[i][1]-=pff;
                pf-=pff;           
             }

            while(s.size()&&s.back()[1]==0) s.pop_back();

            for(int i = t.size()-1; i>=0; i--){
                int pf=min(f, t[i][1]);
                t[i][1]-=pf;
                f-=pf;
            }

            while(t.size()&&t.back()[1]==0) t.pop_back();

            ans=min(ans, calc(k, l, s, t)+l);
       
        }

        return ans;
    }
    else{
        int n=a.size();
        vector<array<long long int, 2>> s, t;
        for(int i=0; i<n; i++){
            if(a[i][0]<=l/2) s.push_back(a[i]);
            else t.push_back(a[i]); 
        }
        long sum=0;

        for(auto i: s){
            sum+=i[1];
        }

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

        long long int ans=1e18;
        ans=calc(k, l, s, t);

  
         if(sum%k){
            long long int f=sum%k;
            long long int pf=k-f;
            swap(f, pf);

            for(int i = s.size()-1; i>=0; i--){
               int pff=min(pf, s[i][1]);
                s[i][1]-=pff;
                pf-=pff;           
             }

            while(s.size()&&s.back()[1]==0) s.pop_back();

            for(int i = t.size()-1; i>=0; i--){
                int pf=min(f, t[i][1]);
                t[i][1]-=pf;
                f-=pf;
            }

            while(t.size()&&t.back()[1]==0) t.pop_back();

            ans=min(ans, calc(k, l, s, t)+l);
       
        }

        s.clear(), t.clear();

         for(int i=0; i<n; i++){
            if(a[i][0]<l/2) s.push_back(a[i]);
            else t.push_back(a[i]); 
        }
        sum=0;

        for(auto i: s){
            sum+=i[1];
        }

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

        ans=min(ans, calc(k, l, s, t));

 
         if(sum%k){
            long long int f=sum%k;
            long long int pf=k-f;
                         swap(f, pf);

            for(int i = s.size()-1; i>=0; i--){
               int pff=min(pf, s[i][1]);
                s[i][1]-=pff;
                pf-=pff;           
             }



            while(s.size()&&s.back()[1]==0) s.pop_back();

            for(int i = t.size()-1; i>=0; i--){
                int pf=min(f, t[i][1]);
                t[i][1]-=pf;
                f-=pf;
            }

            while(t.size()&&t.back()[1]==0) t.pop_back();

            ans=min(ans, calc(k, l, s, t)+l);
       
        }

        return ans;

    }
    return 0;

}

long long int delivery(int n, int k, int l, int p[]) {
    vector<int> a(n);

   for(int i=0; i<n; i++) a[i]=p[i];
    sort(a.begin(), a.end());
    int kk=1;
    vector<array<long long int, 2>> b;

    for(int i=1; i<n; i++){
        if(a[i]==a[i-1]) kk++;
        else{
            if(a[i-1]!=0)
            b.push_back({a[i-1], kk});
            kk=1;
        }
    }

    if(a[n-1]!=0)
    b.push_back({a[n-1], kk});
    
    long long int ans=d(n, k, l, b);

    reverse(b.begin(), b.end());
    for(auto &i: b) i[0]=l-i[0];

  //  ans=min(ans, d(n, k, l, b));
    return ans;
    return 0;
}
/*
int main() {
    f();

    int N, K, L, i;
    cin >> N >> K >> L;


    int *p = (int*)malloc(sizeof(int) * (unsigned int)N);

    for (i = 0; i < N; i++) {
        cin >> p[i];
    }

    cout<<delivery(N, K, L, p);
    return 0;
}*/

Compilation message (stderr)

boxes.cpp: In function 'long long int calc(int, int, std::vector<std::array<long long int, 2> >, std::vector<std::array<long long int, 2> >)':
boxes.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0; i<s.size(); i++){
      |                  ~^~~~~~~~~
boxes.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0; i<t.size(); i++){
      |                  ~^~~~~~~~~
boxes.cpp: In function 'long long int d(int, int, int, std::vector<std::array<long long int, 2> >)':
boxes.cpp:58:12: warning: declaration of 'int n' shadows a parameter [-Wshadow]
   58 |        int n=a.size();
      |            ^
boxes.cpp:54:22: note: shadowed declaration is here
   54 | long long int  d(int n, int k, int l, vector<array<long long int, 2>> a){
      |                  ~~~~^
boxes.cpp:58:20: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |        int n=a.size();
      |              ~~~~~~^~
boxes.cpp:82:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   82 |             for(int i = s.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:83:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |                int pff=min(pf, s[i][1]);
      |                        ~~~^~~~~~~~~~~~~
boxes.cpp:90:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   90 |             for(int i = t.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:91:21: warning: declaration of 'pf' shadows a previous local [-Wshadow]
   91 |                 int pf=min(f, t[i][1]);
      |                     ^~
boxes.cpp:78:27: note: shadowed declaration is here
   78 |             long long int pf=k-f;
      |                           ^~
boxes.cpp:91:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |                 int pf=min(f, t[i][1]);
      |                        ~~~^~~~~~~~~~~~
boxes.cpp:105:13: warning: declaration of 'int n' shadows a parameter [-Wshadow]
  105 |         int n=a.size();
      |             ^
boxes.cpp:54:22: note: shadowed declaration is here
   54 | long long int  d(int n, int k, int l, vector<array<long long int, 2>> a){
      |                  ~~~~^
boxes.cpp:105:21: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  105 |         int n=a.size();
      |               ~~~~~~^~
boxes.cpp:128:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  128 |             for(int i = s.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:129:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  129 |                int pff=min(pf, s[i][1]);
      |                        ~~~^~~~~~~~~~~~~
boxes.cpp:136:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  136 |             for(int i = t.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:137:21: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  137 |                 int pf=min(f, t[i][1]);
      |                     ^~
boxes.cpp:125:27: note: shadowed declaration is here
  125 |             long long int pf=k-f;
      |                           ^~
boxes.cpp:137:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  137 |                 int pf=min(f, t[i][1]);
      |                        ~~~^~~~~~~~~~~~
boxes.cpp:170:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  170 |             for(int i = s.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:171:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  171 |                int pff=min(pf, s[i][1]);
      |                        ~~~^~~~~~~~~~~~~
boxes.cpp:180:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  180 |             for(int i = t.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:181:21: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  181 |                 int pf=min(f, t[i][1]);
      |                     ^~
boxes.cpp:167:27: note: shadowed declaration is here
  167 |             long long int pf=k-f;
      |                           ^~
boxes.cpp:181:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  181 |                 int pf=min(f, t[i][1]);
      |                        ~~~^~~~~~~~~~~~
boxes.cpp:54:22: warning: unused parameter 'n' [-Wunused-parameter]
   54 | long long int  d(int n, int k, int l, vector<array<long long int, 2>> a){
      |                  ~~~~^
boxes.cpp: In function 'void f()':
boxes.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
boxes.cpp:10:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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