Submission #356505

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
356505	2021-01-23T12:29:52 Z	urd05	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	1 ms	492 KB

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]);
        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()&&aind+bind<=n&&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;
}

Compilation message

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

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	492 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	364 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	372 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Incorrect	1 ms	364 KB	Output isn't correct
5	Halted	0 ms	0 KB	-