Submission #893083

#	Time	Username	Problem	Language	Result	Execution time	Memory
893083		8pete8	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	644 ms	493248 KiB

boxes

#include "boxes.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
//#define int long long
using namespace std;
//const int mod=998244353,mxn=2e5+5,lg=30,inf=1e9,minf=-1e9,Mxn=100000;
long long delivery(int N, int K, int L, int p[]) {
    vector<ll>l,r;
    vector<ll>ps(N+1,0),sf(N+1,0);
    vector<ll>cnt(0);
    for(int i=0;i<N;i++){
        if(p[i]==0)continue;
        l.pb(p[i]);
        r.pb(L-p[i]);
    }
    N=l.size();
    for(int i=0;i<N;i++){
        if(i-K<0)ps[i]=l[i]*2;
        else ps[i]=ps[i-K]+l[i]*2;
    }
    for(int i=N-1;i>=0;i--){
        if(i+K>=N)sf[i]=r[i]*2;
        else sf[i]=sf[i+K]+r[i]*2;
    }
    ll ans=(ceil(N*1.0/K)*L);
    ans=min(ans,ps[N-1]);
    ans=min(ans,sf[0]);
    for(int i=N-1;i>=0;i--)if(i+K<N)sf[i]=min(sf[i],sf[i+K]+L);
    for(int i=0;i<N-1;i++)ans=min(ans,ps[i]+sf[i+1]);
    return ans;
}
/*
int32_t main(){
    int n,k,l;cin>>n>>k>>l;
    int v[n];
    for(int i=0;i<n;i++)cin>>v[i];
    cout<<delivery(n,k,l,v);
}*/

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:47:13: warning: conversion from 'std::vector<long long int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   47 |     N=l.size();
      |       ~~~~~~^~
boxes.cpp:56:26: warning: conversion from 'double' to 'long long int' may change value [-Wfloat-conversion]
   56 |     ll ans=(ceil(N*1.0/K)*L);
      |            ~~~~~~~~~~~~~~^~~

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