Submission #356491

#	Time	Username	Problem	Language	Result	Execution time	Memory
356491		urd05	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	364 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[]) {
    long long ret=1LL*((n-1)/k+1)*l;
    vector<int> one;
    vector<int> two;
    one.push_back(0);
    two.push_back(0);
    for(int i=0;i<n;i++) {
        if (p[i]==0) {
            continue;
        }
        if (p[i]<=l/2) {
            one.push_back(p[i]);
        }
        else {
            two.push_back(l-p[i]);
        }
    }
    n=one.size()+two.size()-2;
    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+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+1LL*cnt*l);
    }
    return ret;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:25:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   25 |     n=one.size()+two.size()-2;
      |       ~~~~~~~~~~~~~~~~~~~~~^~
boxes.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=1;i<one.size();i++) {
      |                 ~^~~~~~~~~~~
boxes.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=1;i<two.size();i++) {
      |                 ~^~~~~~~~~~~
boxes.cpp:47:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (i<one.size()&&n%k-i<two.size()&&osum[i]+tsum[n%k-i]<mini) {
      |             ~^~~~~~~~~~~
boxes.cpp:47:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (i<one.size()&&n%k-i<two.size()&&osum[i]+tsum[n%k-i]<mini) {
      |                           ~~~~~^~~~~~~~~~~
boxes.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if (aind+i<one.size()&&bind+k-i<two.size()&&osum[aind+i]+tsum[bind+k-i]<mn) {
      |                 ~~~~~~^~~~~~~~~~~
boxes.cpp:59:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             if (aind+i<one.size()&&bind+k-i<two.size()&&osum[aind+i]+tsum[bind+k-i]<mn) {
      |                                    ~~~~~~~~^~~~~~~~~~~

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