제출 #780335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780335		vjudge1	선물상자 (IOI15_boxes)	C++17	0 / 100	1 ms	340 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 tek(int k, int l, vector<array<long long int, 2>> s, vector<array<long long int, 2>> t){
    long long sum=0;
    long long val=0;
    long long el=0;

    for(int i=s.size()-1; i>=0; i--){
        int f=min(s[i][1], el);
        el-=f;
        s[i][1]-=f;
        int st=s[i][1]/k;
        val+=st*s[i][0];
        el+=st*k;

        f=min(el, s[i][1]);
        s[i][1]-=f;
        el-=f;

    }

    el=0;
    for(int i=t.size()-1; i>=0; i--){
        int f=min(t[i][1], el);
        el-=f;
        t[i][1]-=f;
        int st=t[i][1]/k;
        val+=st*(l-t[i][0]);
        el+=st*k;

        f=min(el, t[i][1]);
        t[i][1]-=f;
        el-=f;

    }

    
    long long int ans=1e18;
    ans=val+calc(k, l, s, t);
  
    for(auto i: s){
        sum+=i[1];
    }

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

    
    }

    return ans;

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

    reverse(t.begin(), t.end());
    long long ans = tek(k, l,s, t);

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

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

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


    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 tek(int, int, std::vector<std::array<long long int, 2> >, std::vector<std::array<long long int, 2> >)':
boxes.cpp:60:23: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   60 |     for(int i=s.size()-1; i>=0; i--){
      |               ~~~~~~~~^~
boxes.cpp:61:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   61 |         int f=min(s[i][1], el);
      |               ~~~^~~~~~~~~~~~~
boxes.cpp:64:23: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   64 |         int st=s[i][1]/k;
boxes.cpp:68:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   68 |         f=min(el, s[i][1]);
      |           ~~~^~~~~~~~~~~~~
boxes.cpp:75:23: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |     for(int i=t.size()-1; i>=0; i--){
      |               ~~~~~~~~^~
boxes.cpp:76:18: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   76 |         int f=min(t[i][1], el);
      |               ~~~^~~~~~~~~~~~~
boxes.cpp:79:23: warning: conversion from 'std::array<long long int, 2>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   79 |         int st=t[i][1]/k;
boxes.cpp:83:14: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |         f=min(el, t[i][1]);
      |           ~~~^~~~~~~~~~~~~
boxes.cpp:105:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  105 |         for(int i = s.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:106:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |            int pff=min(pf, s[i][1]);
      |                    ~~~^~~~~~~~~~~~~
boxes.cpp:113:29: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  113 |         for(int i = t.size()-1; i>=0; i--){
      |                     ~~~~~~~~^~
boxes.cpp:114:17: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  114 |             int pf=min(f, t[i][1]);
      |                 ^~
boxes.cpp:102:23: note: shadowed declaration is here
  102 |         long long int pf=k-f;
      |                       ^~
boxes.cpp:114:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  114 |             int pf=min(f, t[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp:128:29: 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:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  129 |            int pff=min(pf, s[i][1]);
      |                    ~~~^~~~~~~~~~~~~
boxes.cpp:136:29: 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:17: warning: declaration of 'pf' shadows a previous local [-Wshadow]
  137 |             int pf=min(f, t[i][1]);
      |                 ^~
boxes.cpp:102:23: note: shadowed declaration is here
  102 |         long long int pf=k-f;
      |                       ^~
boxes.cpp:137:23: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  137 |             int pf=min(f, t[i][1]);
      |                    ~~~^~~~~~~~~~~~
boxes.cpp: In function 'long long int d(int, int, int, std::vector<std::array<long long int, 2> >)':
boxes.cpp:153:17: warning: conversion from 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  153 |     int n=a.size();
      |           ~~~~~~^~
boxes.cpp:151:22: warning: unused parameter 'N' [-Wunused-parameter]
  151 | 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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30