Submission #28760

#	Time	Username	Problem	Language	Result	Execution time	Memory
28760		repeating	Boxes with souvenirs (IOI15_boxes)	C++11	0 / 100	2 ms	380 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 = 1e8;
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>h){
            ret+=v[i].F*2;
            h=k-v[i].S+h;
            ret+=v[i+1].F-v[i].F;
            i++;
            C;
        }
        if(v[i].S<h){
            h-=v[i].S;
            ret+=v[i+1].F-v[i].F;
            i++;
            C;
        }
        if(v[i].S==h){
            h=k;
            if(i==m-1)ret+=v[i].F;
            else{
                ret+=v[i].F*2;
                ret+=v[i+1].F-v[i].F;
            }
            i++;
        }
    }
    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].S-=s1%k;
        v2.pb({l-v1.back().F,s1%k});
        ret=min(ret,DP(v1)+DP(v2));
        v1[v1.SI].S+=s1%k;
        v2.pop_back();
    }
    if(!v2.empty()&&v2.back().S>s2%k&&s2%k){
        v2[v2.SI].S-=s2%k;
        v1.pb({l-v2.back().F,s2%k});
        ret=min(ret,DP(v1)+DP(v2));
        v2[v2.SI].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;
    ret=bs(n);
    int l=0,r=n;
    W(l<r){
        int mid=(l+r)/2;
        ll r1=bs(mid),r2=bs(mid+1);
        ret=min(ret,min(r1,r2));
//        cout<<mid<<" "<<r1<<endl;
//        cout<<mid+1<<" "<<r2<<endl;
        if(r1<r2){
            l=mid+1;
        }
        else{
            r=mid;
        }
    }
//    bs(1);
    return ret;
}

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;
                 ^~
boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:110:9: warning: declaration of 'l' shadows a global declaration [-Wshadow]
     int l=0,r=n;
         ^
boxes.cpp:25:9: note: shadowed declaration is here
 int n,k,l;
         ^

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