Submission #477380

#	Time	Username	Problem	Language	Result	Execution time	Memory
477380		leaked	Safety (NOI18_safety)	C++14	71 / 100	250 ms	25240 KiB

safety

#include <bits/stdc++.h>


#define m_p make_pair
#define pw2(x) (1LL<<x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define sz(x) (int)x.size()
#define len(x) (int)x.size()
#define pb push_back
#define s second
#define vec vector
#define REP(i, a,b) for(int i=(a);i<(b);i++)
#define REPD(i, a,b) for(int i=(a);i>=(b);--i)
#define file "name"
#define fi first
#define se second
using namespace std;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long, long long> pll;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
void INPUT(bool F=0){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    if(F){
        freopen(file".in","r",stdin);
        freopen(file".out","w",stdout);
    }
}

struct myset{
    multiset<ll> st;
    ll ta=0;
    void add(ll x){
        x-=ta;
        st.insert(x);
    }
    ll gb(){
        assert(sz(st));
        return *st.rbegin()+ta;
    }
    ll gf(){
        assert(sz(st));
        return *st.begin()+ta;
    }
};
signed main(){
    INPUT();
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    myset l,r;
    int n,t;
    cin>>n>>t;
    ll ans=1e18;
    ll k=0,b=0;
    auto insrt=[&](ll x){
        l.add(x);l.add(x);k++;b-=x;
        while(sz(l.st)!=sz(r.st)){
            ll y=l.gb();l.st.erase(--l.st.end());
            r.add(y);
        }
    };
    auto fix=[&](){
        while(r.gf()<l.gb()){
            ll x=l.gb();ll y=r.gf();
            l.st.erase(--l.st.end());r.st.erase(r.st.begin());
            l.add(y);r.add(x);
        }
    };
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        l.ta-=t;r.ta+=t;b-=1ll*sz(r.st)*t;
        insrt(x);fix();
//        for(auto &q : l.st) debug()<<imie(q+l.ta);
//        for(auto &q : r.st) debug()<<imie(q+r.ta);
//        cout<<endl;
//        debug()<<imie(k);
    }
//    debug()<<imie(b)imie(k);
    vec<ll>xs;
    while(sz(l.st)) xs.pb(l.gf()),l.st.erase(l.st.begin());
    while(sz(r.st)) xs.pb(r.gf()),r.st.erase(r.st.begin());
    reverse(all(xs));
    for(auto &x : xs){
        umin(ans,1ll*k*x+b);
        k--;b+=x;
    }
    cout<<ans;
    return 0;
}
/*
#fwxpd bf
fwxpdbf
dpinbmcrfwxpdbf
*/

Compilation message (stderr)

safety.cpp: In function 'void INPUT(bool)':
safety.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(file".in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
safety.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(file".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 0 / 29