Submission #28763

#	Time	Username	Problem	Language	Result	Execution time	Memory
28763		repeating	Boxes with souvenirs (IOI15_boxes)	C++11	0 / 100	8 ms	376 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e16;
const int MX=1000015;
int n,k,l;
pii a[MX];
ll DP(vector<pii> &v){
    int s=0,m=v.SI;
    for(int i=0;i<m;i++){
        s+=v[i].S;
    }
    ll ret=0;
    int i=0;
    int h=s%k;
    if(h==0)h=k;
    W(i<m){
        if(v[i].S%k==h%k){
            h=k;
//            cout<<'z';
            if(i==m-1){
                ret+=v[i].F;
                if(v[i].S>h)ret+=((v[i].S/k)*v[i].F*2);
            }
            else{
                ret+=(v[i].S/k)*2*v[i].F;
                ret+=v[i].F*2;
                ret+=v[i+1].F-v[i].F;
            }
            i++;
            C;
        }
        if(v[i].S%k>h){
//            cout<<'d';
            ret+=(v[i].S/k)*2*v[i].F;
            ret+=v[i].F*2;
            h=k-v[i].S%k+h;
            ret+=v[i+1].F-v[i].F;
            i++;
            C;
        }
        if(v[i].S%k<h){
//            cout<<'s';
            ret+=(v[i].S/k)*2*v[i].F;
            h-=v[i].S%k;
            ret+=v[i+1].F-v[i].F;
            i++;
            C;
        }
    }
    if(v.SI)
        ret+=v[0].F;
//    cout<<ret<<"        ";
//    for(int i=0;i<v.SI;i++)
//        cout<<v[i].F<<','<<v[i].S<<" ";
//    cout<<endl;
    R ret;
}
ll bs(int mid){
    vector<pii> v1,v2;
    ll ret=0;
    int s1=0,s2=0;
    for(int i=0;i<mid;i++){
        v1.pb(a[i]);
        s1+=a[i].S;
    }
    for(int i=n-1;i>=mid;i--){
        v2.pb({l-a[i].F,a[i].S});
        s2+=a[i].S;
    }
    ret=DP(v1)+DP(v2);
    if(!v1.empty()&&v1.back().S>s1%k&&s1%k){
        v1[v1.SI-1].S-=s1%k;
        v2.pb({l-v1.back().F,s1%k});
        ret=min(ret,DP(v1)+DP(v2));
        v1[v1.SI-1].S+=s1%k;
        v2.pop_back();
    }
    if(!v2.empty()&&v2.back().S>s2%k&&s2%k){
        v2[v2.SI-1].S-=s2%k;
        v1.pb({l-v2.back().F,s2%k});
        ret=min(ret,DP(v1)+DP(v2));
        v2[v2.SI-1].S+=s2%k;
        v1.pop_back();
    }
    R ret;
}
long long delivery(int N, int K, int L, int p[]) {
    n=N,k=K,l=L;
    sort(p,p+n);
    int j=0;
    for(int i=0;i<n;j++,i++){
        a[j].F=p[i];
        a[j].S=1;
        W(i<n-1&&p[i]==p[i+1])
            a[j].S++,i++;
    }
    n=j;
    ll ret=INF;
    for(int i=1;i<n;i++)
        ret=min(ret,bs(i));
//    bs(1);
    return ret;
}

//static char _buffer[1024];
//static int _currentChar = 0;
//static int _charsNumber = 0;
//static FILE *_inputFile, *_outputFile;
//
//int main() {
//
//
//    int N, K, L, i;
//    cin>>N>>K>>L;
//    int p[N+1];
//    for (i = 0; i < N; i++) {
//        cin>>p[i];
//    }
//
//    printf("%lld\n", delivery(N, K, L, p));
//    return 0;
//}

Compilation message (stderr)

boxes.cpp: In function 'long long int DP(std::vector<std::pair<int, int> >&)':
boxes.cpp:11:16: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
 #define SI size()
                ^
boxes.cpp:28:17: note: in expansion of macro 'SI'
     int s=0,m=v.SI;
                 ^~

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