제출 #356510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
356510		urd05	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	773 ms	287040 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
 
long long osum[10000001];
long long tsum[10000001];
 
long long delivery(int n,int k,int l,int p[]) {
    vector<int> one;
    vector<int> two;
    one.push_back(0);
    two.push_back(0);
    for(int i=0;i<n;i++) {
        one.push_back(p[i]);
    }
    for(int i=n-1;i>=0;i--) {
        two.push_back(l-p[i]);
    }
    long long ret=1LL*((n-1)/k+1)*l;
    int aind=0;
    int bind=0;
    for(int i=1;i<one.size();i++) {
        if (i>=k) {
            osum[i]=osum[i-k]+one[i];
        }
        else {
            osum[i]=one[i];
        }
    }
    for(int i=1;i<two.size();i++) {
        if (i>=k) {
            tsum[i]=tsum[i-k]+two[i];
        }
        else {
            tsum[i]=two[i];
        }
    }
    int pos=-1;
    long long mini=1e18;
    for(int i=0;i<=n%k;i++) {
        if (i<one.size()&&n%k-i<two.size()&&osum[i]+tsum[n%k-i]<mini) {
            mini=osum[i]+tsum[n%k-i];
            pos=i;
        }
    }
    aind=pos;
    bind=n%k-pos;
    ret=min(ret,mini*2+1LL*(n/k)*l);
    for(int cnt=n/k-1;cnt>=0;cnt--) {
        long long mn=1e18;
        pos=-1;
        for(int i=0;i<=k;i++) {
            if (aind+i<one.size()&&bind+k-i<two.size()&&osum[aind+i]+tsum[bind+k-i]<mn) {
                mn=osum[aind+i]+tsum[bind+k-i];
                pos=i;
            }
        }
        aind+=pos;
        bind+=k-pos;
        ret=min(ret,mn*2+1LL*cnt*l);
    }
    return ret;
}

컴파일 시 표준 에러 (stderr) 메시지

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=1;i<one.size();i++) {
      |                 ~^~~~~~~~~~~
boxes.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i=1;i<two.size();i++) {
      |                 ~^~~~~~~~~~~
boxes.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if (i<one.size()&&n%k-i<two.size()&&osum[i]+tsum[n%k-i]<mini) {
      |             ~^~~~~~~~~~~
boxes.cpp:41:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if (i<one.size()&&n%k-i<two.size()&&osum[i]+tsum[n%k-i]<mini) {
      |                           ~~~~~^~~~~~~~~~~
boxes.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (aind+i<one.size()&&bind+k-i<two.size()&&osum[aind+i]+tsum[bind+k-i]<mn) {
      |                 ~~~~~~^~~~~~~~~~~
boxes.cpp:53:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if (aind+i<one.size()&&bind+k-i<two.size()&&osum[aind+i]+tsum[bind+k-i]<mn) {
      |                                    ~~~~~~~~^~~~~~~~~~~

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