結果

問題 No.3683 サーバー代がもったいない!
コンテスト
ユーザー 541
提出日時 2026-09-05 19:35:16
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 82 ms / 2,000 ms
+ 148µs
コード長 4,494 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,619 ms
コンパイル使用メモリ 359,892 KB
実行使用メモリ 87,424 KB
最終ジャッジ日時 2026-09-05 19:35:37
合計ジャッジ時間 8,719 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=int64_t;
using ull=uint64_t;
using lll=__int128_t;
using ulll=__uint128_t;

using db=double;
using ld=long double;

using pint=pair<int,int>;
using pill=pair<int,ll>;
using pll=pair<ll,ll>;
using plli=pair<ll,int>;

template<typename T1,typename T2>
using unmap=unordered_map<T1,T2>;
template<typename T>
using unset=unordered_set<T>;

template<typename T>
using heap=priority_queue<T>;
template<typename T>
using min_heap=priority_queue<T,vector<T>,greater<T>>;

namespace rgs=ranges;

#define rep(i,l,r) for(ll i=(ll)(l);i<(ll)(r);i++)
#define per(i,r,l) for(ll i=(ll)(r);i>=(ll)(l);i--)

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

#define ep emplace
#define ef emplace_front
#define pof pop_front
#define eb emplace_back
#define pob pop_back

#define fi first
#define se second

#define YES cout<<"Yes\n"
#define NO cout<<"No\n"
#define YN(flag) (flag) ? YES:NO
#define ENDL cout<<'\n'

const int INF32=(1<<30)-1;
const ll INF64=(1ll<<62)-1;
const ll MOD99=998244353;
const ll MOD10=1000000007;
const ld PI=acosl(-1);

const array<int,8> di={1,0,-1,0,-1,1,-1,1};
const array<int,8> dj={0,1,0,-1,-1,1,1,-1};

template<typename T1,typename T2>
istream& operator>>(istream &is,pair<T1,T2> &x){ return is>>x.fi>>x.se; }
template<typename T1,typename T2>
ostream& operator<<(ostream &os,const pair<T1,T2> &x){ return os<<x.fi<<' '<<x.se; }

template<typename T>
istream& operator>>(istream &is,vector<T> &vec){ rep(i,0,size(vec)) is>>vec[i]; return is; }
template<typename T>
ostream& operator<<(ostream &os,const vector<T> &vec){ rep(i,0,size(vec)) (i==0 ? os<<vec[i]:os<<' '<<vec[i]); return os; }
template<typename T>
ostream& operator<<(ostream &os,const vector<vector<T>> &vec){ rep(i,0,size(vec)) (i==0 ? os<<vec[i]:os<<'\n'<<vec[i]); return os; }

template<typename T,size_t N>
istream& operator>>(istream &is,array<T,N> &arr){ rep(i,0,N) is>>arr[i]; return is; }
template<typename T,size_t N>
ostream& operator<<(ostream &os,const array<T,N> &arr){ rep(i,0,N) (i==0 ? os<<arr[i]:os<<' '<<arr[i]); return os; }

template<typename T>
ostream& operator<<(ostream &os,const set<T> &st){ size_t i=0; for(T x : st) (i++==0 ? os<<x:os<<' '<<x); return os; }
template<typename T>
ostream& operator<<(ostream &os,const multiset<T> &mst){ size_t i=0; for(T x : mst) (i++==0 ? os<<x:os<<' '<<x); return os; }

void input(){ 'v'; }
template<typename Head,typename... Tail>
void input(Head &head,Tail&... tail){ cin>>head; input(tail...); }

void output(){ 'v'; }
template<typename Head,typename... Tail>
void output(const Head &head,const Tail&... tail){ cout<<head; if(sizeof...(tail)>0) cout<<' '; output(tail...); }

void outputln(){ ENDL; }
template<typename Head,typename... Tail>
void outputln(const Head &head,const Tail&... tail){ cout<<head; if(sizeof...(tail)>0) cout<<' '; outputln(tail...); }

void outputlines(){ ENDL; }
template<typename Head,typename... Tail>
void outputlines(const Head &head,const Tail&... tail){ cout<<head; if(sizeof...(tail)>0) cout<<'\n'; outputlines(tail...); }

void lines(int n=10){ while(n--) cout<<'-'; ENDL; }

template<typename T>
bool chmax(T &a,const T &b){ return (a<b ? (a=b,true):false); }
template<typename T>
bool chmin(T &a,const T &b){ return (a>b ? (a=b,true):false); }

template<typename T>
bool outside(const T &i,const T &j,const T &h,const T &w) { return (i<0 or i>=h or j<0 or j>=w); }

template<typename T>
T divfloor(T x,T y ){ if(y<0) x*=(-1),y*=(-1); return(x>=0 ? x/y:(x-y+1)/y); }
template<typename T>
T divceil(T x,T y) { if(y<0) x*=(-1),y*=(-1); return(x>=0 ? (x+y-1)/y:x/y); }

void flip(bool& b) { b^=1; }

////////////////////////////////////////////////////////////////////////////////


bool solve(){
    int n,k;
    input(n,k);

    vector<int> a(n);
    input(a);
    
    if(divceil(n,2)<k){
        outputln("Impossible");
        return 0;
    }

    vector dp(n+1,vector<array<ll,2>>(k+1,array<ll,2>({-INF64,-INF64})));
    dp[0][0][false]=0;
    rep(i,0,n){
        rep(j,0,k+1){
            // a[i] を BAN しない場合
            chmax(dp[i+1][j][false],rgs::max(dp[i][j]));

            // BAN する場合
            if(j+1<=k) chmax(dp[i+1][j+1][true],dp[i][j][false]+a[i]);
        }
    }
    outputln(rgs::max(dp[n][k]));

    return 0;
}

int main(){
    cout<<fixed<<setprecision(20);

    int t=1;
    //cin>>t;

    while(t--) while(solve());

    return 0;
}
0