Submission #780269

#	Time	Username	Problem	Language	Result	Execution time	Memory
780269		vjudge1	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	2080 ms	87940 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;
    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);

    vector< array<long long int, 2>> ss, tt;
        ss = s; tt= t;
        for(int pf=1; pf<k; pf++){

        
        long long int f=k-pf;
        long long int e=pf;


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

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

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

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

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


    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));

        ss = s; tt= t;
        for(int pf=1; pf<k; pf++){

        
        long long int f=k-pf;
        long long int e=pf;


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

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

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

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

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

    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:17: 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:84:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   84 |         for(int i = s.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:85:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |            int pff=min(e, s[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp:92:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   92 |         for(int i = t.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:93:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |             int pff=min(f, t[i][1]);
      |                     ~~~^~~~~~~~~~~~
boxes.cpp:130:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  130 |         for(int i = s.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:131:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  131 |            int pff=min(e, s[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp:138:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  138 |         for(int i = t.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:139:24: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  139 |             int pff=min(f, t[i][1]);
      |                     ~~~^~~~~~~~~~~~
boxes.cpp:56:22: warning: unused parameter 'N' [-Wunused-parameter]
   56 | 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