제출 #780260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780260		vjudge1	선물상자 (IOI15_boxes)	C++17	50 / 100	302 ms	87100 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);


     if(sum%k){
        vector< array<long long int, 2>> ss, tt;
        ss=s; tt=t;

        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=ss; t=tt;

        f=sum%k;
        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;           
         }

        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){
        vector< array<long long int, 2>> ss, tt;
        ss=s; tt=t;

        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=ss; t=tt;

        f=sum%k;
        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;           
         }

        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;
}*/

컴파일 시 표준 에러 (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(pf, 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:17: warning: declaration of 'pf' shadows a previous local [-Wshadow]
   93 |             int pf=min(f, t[i][1]);
      |                 ^~
boxes.cpp:81:23: note: shadowed declaration is here
   81 |         long long int pf=k-f;
      |                       ^~
boxes.cpp:93:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   93 |             int pf=min(f, t[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp:107:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  107 |         for(int i = s.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:108:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  108 |            int pff=min(pf, s[i][1]);
      |                    ~~~^~~~~~~~~~~~~
boxes.cpp:115:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |         for(int i = t.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:116:17: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  116 |             int pf=min(f, t[i][1]);
      |                 ^~
boxes.cpp:81:23: note: shadowed declaration is here
   81 |         long long int pf=k-f;
      |                       ^~
boxes.cpp:116:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  116 |             int pf=min(f, t[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp:152:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  152 |         for(int i = s.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:153:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  153 |            int pff=min(pf, s[i][1]);
      |                    ~~~^~~~~~~~~~~~~
boxes.cpp:160:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  160 |         for(int i = t.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:161:17: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  161 |             int pf=min(f, t[i][1]);
      |                 ^~
boxes.cpp:149:23: note: shadowed declaration is here
  149 |         long long int pf=k-f;
      |                       ^~
boxes.cpp:161:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  161 |             int pf=min(f, t[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp:175:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  175 |         for(int i = s.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:176:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  176 |            int pff=min(pf, s[i][1]);
      |                    ~~~^~~~~~~~~~~~~
boxes.cpp:183:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  183 |         for(int i = t.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:184:17: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  184 |             int pf=min(f, t[i][1]);
      |                 ^~
boxes.cpp:149:23: note: shadowed declaration is here
  149 |         long long int pf=k-f;
      |                       ^~
boxes.cpp:184:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  184 |             int pf=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