Submission #704628

#	Time	Username	Problem	Language	Result	Execution time	Memory
704628		Alihan_8	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	7 ms	340 KiB

boxes

#include <bits/stdc++.h>
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
long long delivery(int n, int k, int L, int P[]){
    map <int,int> mp;
    for ( int i = 0; i < n; i++ ){
        if ( !P[i] ) continue;
        mp[P[i]]++;
    }
    int sz = (int)mp.size();
    vector <pair<int,long long>> p;
    for ( auto [it, val]: mp ) p.pb({it, val});
//    for ( auto [it, val]: p ) cout << it << ' ' << val << ln; cout << ln;
    auto f = [&](int it){
        long long cnt = p[it].first*2, rem = 0;
        for ( int i = it; i >= 0; i-- ){
            auto [pos, freq] = p[i];
            if ( it == i ){
                if ( freq >= k ) freq -= k;
                else{
                    freq = 0, rem = k-freq;
                    continue;
                }
            }
            long long Mn = min(rem, freq);
            freq -= Mn, rem -= Mn;
            long long val = (freq+k-1)/k;
            rem = val*k-freq;
            cnt += pos*val*2;
        }
        return cnt;
    };
    vector <long long> pref(sz), suff(sz);
    for ( int i = 0; i < sz; i++ ){
        pref[i] = f(i);
    }
    reverse(all(p));
    for ( auto &[it, val]: p ) it = L-it;
    for ( int i = 0; i < sz; i++ ){
        suff[sz-i-1] = f(i);
    }
    long long Mn = min(pref.back(), suff[0]);
    for ( int i = 0; i+1 < sz; i++ ){
        Mn = min(Mn, pref[i]+suff[i+1]);
    }
    return Mn;
}
#if false
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k, L; cin >> n >> k >> L;
    int p[n];
    for ( int i = 0; i < n; i++ ) cin >> p[i];
    cout << delivery(n, k, L, p);

    cout << '\n';
/*
3 2 8
1 2 5
answer : 10
*/
}
#endif

Compilation message (stderr)

boxes.cpp: In function 'void IO(std::string)':
boxes.cpp:11:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boxes.cpp:11:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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