제출 #1354905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1354905		kokokai	Candies (JOI18_candies)	C++20	100 / 100	245 ms	15068 KiB

candies

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define task "text"
#define int long long
const int N = 200001;
int a[N];
int n;
vector<ll> merg(vector<ll> a,vector<ll> b){
    int i1=0,i2=0;
    vector<ll> r;
    r.push_back(0LL);
    while(i1+1 < a.size() || i2+1 < b.size()){
        int v1,v2;
        if(i1+1 < a.size()) v1=a[i1+1]-a[i1];
        else v1=-9e17;
        if(i2+1 < b.size()) v2=b[i2+1]-b[i2];
        else v2=-9e17;
        if(v1 >= v2){
            i1++;
            r.push_back(a[i1]+b[i2]);
        }else{
            i2++;
            r.push_back(a[i1]+b[i2]);
        }
    }
    return r;
}
vector<ll> comb(vector<ll> a,vector<ll> b){
    if(a.size()>b.size()) swap(a,b);
    vector<ll> re;
    for(int i=0;i<a.size();i++){
        re.push_back(max(a[i],b[i]));
    }
    for(int i=a.size();i<b.size();i++){
        re.push_back(b[i]);
    }
    return re;
}
vector<vector<int>> dnc(int l,int r){
    //cerr<<l<<' '<<r<<'\n';
    if(l == r){
        vector<vector<ll>> res;
        vector<ll> ret;
        ret.push_back(0LL);
        ret.push_back(a[l]);
        res.push_back(ret);
        ret.clear();
        ret.push_back(0LL);
        for(int i=0;i<3;i++) res.push_back(ret);
        return res;
    }
    int mid=(l+r)>>1;
    vector<vector<ll>> lef=dnc(l,mid);
    vector<vector<ll>> rig=dnc(mid+1,r);
    vector<vector<ll>> v;
    //0:co the chon hoac ko
    //1: bat buoc ko chon
    //00
    v.push_back(comb(merg(lef[1],rig[0]),merg(lef[0],rig[2])));
    //01
    v.push_back(comb(merg(lef[0],rig[3]),merg(lef[1],rig[1])));
    //10
    v.push_back(comb(merg(lef[2],rig[2]),merg(lef[3],rig[0])));
    //11
    v.push_back(comb(merg(lef[2],rig[3]),merg(lef[3],rig[1])));
    return v;
}
int ans[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
    }
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<vector<ll>> v=dnc(1,n);
    for(int i=1;i<=(n+1)/2;i++){
        cout<<v[0][i]<<'\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'int main()':
candies.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92