Submission #780224

#	Time	Username	Problem	Language	Result	Execution time	Memory
780224		vjudge1	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	115 ms	71036 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 calc(int k, int l, vector<array<long long, 2>> s, vector<array<long long, 2>> t){
    long long ans = 0;

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

    long long p=0;  


    for(int i=0; i<s.size(); i++){
        long long 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 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, 2>> a){  
    if(!a.size()) return 0;

    if(l%2==0){
       int n=a.size();
       vector<array<long long, 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]); 
        }
        int sum=0;


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

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

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

         if(sum%k){
            long long f=sum%k;
            long long 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, 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]); 
        }
        int sum=0;

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

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

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

  
         if(sum%k){
            long long f=sum%k;
            long long 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 f=sum%k;
            long long pf=k-f;

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

                         swap(f, pf);


            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 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, 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 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:35: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]
   35 |     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:56:12: warning: declaration of 'int n' shadows a parameter [-Wshadow]
   56 |        int n=a.size();
      |            ^
boxes.cpp:52:21: note: shadowed declaration is here
   52 | long long int d(int n, int k, int l, vector<array<long long, 2>> a){
      |                 ~~~~^
boxes.cpp:56:20: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |        int n=a.size();
      |              ~~~~~~^~
boxes.cpp:66:21: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   66 |             sum+=i[1];
      |                     ^
boxes.cpp:80:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   80 |             for(int i = s.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:81:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   81 |                int pff=min(pf, s[i][1]);
      |                        ~~~^~~~~~~~~~~~~
boxes.cpp:88:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   88 |             for(int i = t.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:89:21: warning: declaration of 'pf' shadows a previous local [-Wshadow]
   89 |                 int pf=min(f, t[i][1]);
      |                     ^~
boxes.cpp:76:23: note: shadowed declaration is here
   76 |             long long pf=k-f;
      |                       ^~
boxes.cpp:89:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |                 int pf=min(f, t[i][1]);
      |                        ~~~^~~~~~~~~~~~
boxes.cpp:103:13: warning: declaration of 'int n' shadows a parameter [-Wshadow]
  103 |         int n=a.size();
      |             ^
boxes.cpp:52:21: note: shadowed declaration is here
   52 | long long int d(int n, int k, int l, vector<array<long long, 2>> a){
      |                 ~~~~^
boxes.cpp:103:21: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  103 |         int n=a.size();
      |               ~~~~~~^~
boxes.cpp:112:21: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  112 |             sum+=i[1];
      |                     ^
boxes.cpp:126:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  126 |             for(int i = s.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:127:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  127 |                int pff=min(pf, s[i][1]);
      |                        ~~~^~~~~~~~~~~~~
boxes.cpp:134:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  134 |             for(int i = t.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:135:21: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  135 |                 int pf=min(f, t[i][1]);
      |                     ^~
boxes.cpp:123:23: note: shadowed declaration is here
  123 |             long long pf=k-f;
      |                       ^~
boxes.cpp:135:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  135 |                 int pf=min(f, t[i][1]);
      |                        ~~~^~~~~~~~~~~~
boxes.cpp:155:21: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  155 |             sum+=i[1];
      |                     ^
boxes.cpp:167:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  167 |             for(int i = s.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:168:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  168 |                int pff=min(pf, s[i][1]);
      |                        ~~~^~~~~~~~~~~~~
boxes.cpp:178:33: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  178 |             for(int i = t.size()-1; i>=0; i--){
      |                         ~~~~~~~~^~
boxes.cpp:179:21: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  179 |                 int pf=min(f, t[i][1]);
      |                     ^~
boxes.cpp:165:23: note: shadowed declaration is here
  165 |             long long pf=k-f;
      |                       ^~
boxes.cpp:179:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  179 |                 int pf=min(f, t[i][1]);
      |                        ~~~^~~~~~~~~~~~
boxes.cpp:52:21: warning: unused parameter 'n' [-Wunused-parameter]
   52 | long long int d(int n, int k, int l, vector<array<long long, 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