#1029213 (C++23) No.2261 Coffee

• 問題: No.2261 Coffee
• ユーザー: eQe
• 提出日時: 2024-12-01 01:14:20
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 447 ms / 2,000 ms
• コード長: 4,934 bytes
• コンパイル時間: 5,928 ms
• コンパイル使用メモリ: 317,504 KB
• 実行使用メモリ: 78,044 KB
• 最終ジャッジ日時: 2024-12-01 01:14:39
• 合計ジャッジ時間: 17,827 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,820 KB
testcase_02	AC	2 ms; 6,820 KB
testcase_03	AC	2 ms; 6,820 KB
testcase_04	AC	2 ms; 6,816 KB
testcase_05	AC	2 ms; 6,816 KB
testcase_06	AC	2 ms; 6,816 KB
testcase_07	AC	2 ms; 6,816 KB
testcase_08	AC	2 ms; 6,820 KB
testcase_09	AC	2 ms; 6,820 KB
testcase_10	AC	2 ms; 6,824 KB
testcase_11	AC	2 ms; 6,816 KB
testcase_12	AC	3 ms; 6,816 KB
testcase_13	AC	2 ms; 6,820 KB
testcase_14	AC	2 ms; 6,816 KB
testcase_15	AC	2 ms; 6,816 KB
testcase_16	AC	3 ms; 6,816 KB
testcase_17	AC	12 ms; 6,820 KB
testcase_18	AC	12 ms; 6,816 KB
testcase_19	AC	11 ms; 6,820 KB
testcase_20	AC	10 ms; 6,820 KB
testcase_21	AC	12 ms; 6,816 KB
testcase_22	AC	10 ms; 6,816 KB
testcase_23	AC	13 ms; 6,820 KB
testcase_24	AC	447 ms; 77,420 KB
testcase_25	AC	361 ms; 76,492 KB
testcase_26	AC	439 ms; 77,864 KB
testcase_27	AC	408 ms; 77,348 KB
testcase_28	AC	334 ms; 76,768 KB
testcase_29	AC	331 ms; 76,760 KB
testcase_30	AC	238 ms; 41,720 KB
testcase_31	AC	391 ms; 77,828 KB
testcase_32	AC	392 ms; 78,044 KB
testcase_33	AC	399 ms; 77,920 KB
testcase_34	AC	391 ms; 77,912 KB
testcase_35	AC	388 ms; 77,844 KB
testcase_36	AC	400 ms; 77,848 KB
testcase_37	AC	391 ms; 77,916 KB
testcase_38	AC	436 ms; 77,920 KB
testcase_39	AC	434 ms; 78,040 KB
testcase_40	AC	436 ms; 78,044 KB
testcase_41	AC	442 ms; 78,040 KB
testcase_42	AC	435 ms; 78,040 KB
testcase_43	AC	434 ms; 77,920 KB
testcase_44	AC	439 ms; 78,044 KB

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
namespace my{
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define VVL(n,m,...) vec<vec<ll>>__VA_ARGS__;setsize({n,m},__VA_ARGS__);lin(__VA_ARGS__)
#define FO(n) for(ll ij=n;ij--;)
#define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i<i##stop;i+=i##step)
#define fo(i,...) FO##__VA_OPT__(R)(i __VA_OPT__(,__VA_ARGS__))
#define of(i,...) for(auto[i,i##stop,i##step]=range(1,__VA_ARGS__);i>=i##stop;i-=i##step)
#define fe(a,i,...) for(auto&&__VA_OPT__([)i __VA_OPT__(,__VA_ARGS__]):a)
#define single_testcase void solve();}int main(){my::io();my::solve();}namespace my{
void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);}
using ll=long long;
template<class...A>constexpr auto range(bool s,A...a){array<ll,3>r{0,0,1};ll I=0;((r[I++]=a),...);if(!s&&I==1)swap(r[0],r[1]);r[0]-=s;return r;}
constexpr char nl=10;
constexpr char sp=32;
constexpr auto zz(auto x){return x<0?-x:x;}
constexpr ll pw2(ll n){return 1LL<<n;}
constexpr ll at2(auto x,ll i){return x>>i&1;}
constexpr ll log2_floor(auto x){ll r=0;while(x>1)x>>=1,++r;return r;}
bool amax(auto&a,const auto&b){return a<b?a=b,1:0;}

template<class T>ostream&operator<<(ostream&o,const multiset<T>&s){fe(s,e)o<<e<<string(&e!=&*s.rbegin(),sp);return o;}

template<class T>struct multiset:std::multiset<T>{
  multiset(const initializer_list<T>&a={}){fe(a,e)this->emplace(e);}
  multiset(const vector<T>&a){fe(a,e)this->emplace(e);}
};

template<class T>struct set:multiset<T>{
  using multiset<T>::multiset;
};

template<class V>concept vectorial=is_base_of_v<vector<typename V::value_type>,V>;
template<class T>struct vec_attr{using core_type=T;static constexpr int d=0;};
template<vectorial V>struct vec_attr<V>{using core_type=typename vec_attr<typename V::value_type>::core_type;static constexpr int d=vec_attr<typename V::value_type>::d+1;};
template<class T>using core_t=vec_attr<T>::core_type;
template<class V>istream&operator>>(istream&i,vector<V>&v){fe(v,e)i>>e;return i;}
template<class V>ostream&operator<<(ostream&o,const vector<V>&v){fe(v,e)o<<e<<string(&e!=&v.back(),vectorial<V>?nl:sp);return o;}

template<class V>struct vec:vector<V>{
  using vector<V>::vector;
  vec(const vector<V>&v){vector<V>::operator=(v);}

  vec&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;}
  vec operator^(const vec&u)const{return vec{*this}^=u;}
  vec&operator++(){fe(*this,e)++e;return*this;}
  vec&operator--(){fe(*this,e)--e;return*this;}
  vec operator-()const{vec v=*this;fe(v,e)e=-e;return v;}
};
template<class T=ll,size_t n,size_t i=0>auto make_vec(const ll(&s)[n],T x={}){if constexpr(n==i+1)return vec<T>(s[i],x);else{auto X=make_vec<T,n,i+1>(s,x);return vec<decltype(X)>(s[i],X);}}
template<ll n,class...A>void setsize(const ll(&l)[n],A&...a){((a=make_vec(l,core_t<A>())),...);}

template<bool is_negative=false>struct infinity{
  template<integral T>constexpr operator T()const{return numeric_limits<T>::max()*(1-is_negative*2);}
  template<floating_point T>constexpr operator T()const{return static_cast<ll>(*this);}
  template<class T>constexpr bool operator==(T x)const{return static_cast<T>(*this)==x;}
  constexpr auto operator-()const{return infinity<!is_negative>();}
};
constexpr infinity oo;

void lin(auto&...a){(cin>>...>>a);}
template<char c=sp>void pp(const auto&...a){ll n=sizeof...(a);((cout<<a<<string(--n>0,c)),...);cout<<nl;}

namespace sgt{
template<class S,S op(S,S),S e()>struct segtree{
  ll n,A,log;vec<S>d;
  segtree(ll n):segtree(vec<S>(n,e())){}
  segtree(const vec<S>&v):n(v.size()){log=log2_floor((n-1)|1)+1,A=pw2(log),d.resize(A*2,e());fo(i,n)d[i+A]=v[i];of(i,A-1)update(i+1);}
  ll size()const{return n;}
  void update(ll i){d[i]=op(d[i*2],d[i*2+1]);}
  void set(ll i,S x){assert(0<=i&&i<n);i+=A;d[i]=x;fo(j,1,log+1)update(i>>j);}
  S get(ll i)const{assert(0<=i&&i<n);return d[i+A];}
  S operator[](ll i)const{assert(0<=i&&i<n);return d[i+A];}
  S prod(ll l,ll r){
    assert(0<=l&&l<=r&&r<=n);
    S sml=e(),smr=e();
    l+=A,r+=A;
    while(l<r){if(l&1)sml=op(sml,d[l++]);if(r&1)smr=op(d[--r],smr);l>>=1,r>>=1;}
    return op(sml,smr);
  }

  friend auto&operator<<(ostream&o,const segtree&s){fo(i,s.size())o<<s.get(i)<<string(i!=s.size()-1,sp);return o;}
};
template<class T,auto x=T{}>T sgt_e(){return x;}
template<class T>T sgt_min(T a,T b){return a<b?a:b;}

template<class T>struct segmin:atcoder::segtree<T,sgt_min<T>,sgt_e<T,oo>>{
  using atcoder::segtree<T,sgt_min<T>,sgt_e<T,oo>>::segtree;
};
}

single_testcase
void solve(){
  LL(N);
  constexpr ll A=5;
  VVL(N,A,a);

  vec<sgt::segmin<ll>>smin(pw2(A),sgt::segmin<ll>(N));

  fo(i,N){
    fo(S,pw2(A)){
      ll t=0;
      fo(j,A){
        if(at2(S,j))t+=a[i][j];
        else t-=a[i][j];
      }
      smin[S].set(i,t);
    }
  }

  fo(i,N){
    ll res=0;
    fo(S,pw2(A))amax(res,zz(smin[S].get(i)-smin[S].prod(0,N)));
    pp(res);
  }
}}