Submission #1315182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315182		arman.khachatryan	Gift (IZhO18_nicegift)	C++20	100 / 100	649 ms	104512 KiB

nicegift

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ll n, k;
    cin>>n>>k;
    vector<ll> a(n);
    ll sum=0, mx=0;
    for(ll i=0; i<n; i++){
        cin>>a[i];
        sum+=a[i];
        mx=max(mx, a[i]);
    }
    if(mx>sum/k || sum%k!=0){
        cout<<-1;
        return 0;
    }
    vector<pair<ll, ll>> v;
    ll cur=0;
    v.push_back({a[0], 1});
    for(ll i=0; i<n; i++){
        if(cur+a[i]<=sum/k){
            cur+=a[i];
        }else{
            cur=a[i]-sum/k+cur;
            v.push_back({cur, i+1});
        }
        if(cur==sum/k){
            cur=0;
            if(i+1<n){
                v.push_back({a[i+1], i+2});
            }
        }
    }
    ll mn, y=0;
    vector<vector<ll>> ans(n);
    while(sum>0){
        mn=LLONG_MAX;
        for(auto& it:v){
            mn=min(it.first, mn);
            ans[y].push_back(it.second);
        }
        ans[y].push_back(min(mn, sum/k));
        for(ll i=0; i<k; i++){
            v[i].first-=mn;
            if(v[i].first==0){
                v[i]={a[v[i].second], v[i].second+1};
            }
        }
        y++;
        sum-=mn*k;
    }
    cout<<y<<'\n';
    for(ll i=0; i<n; i++){
        for(ll j=ans[i].size()-1; j>=0; j--){
            cout<<ans[i][j]<<" ";
        }
        cout<<'\n';
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 51 / 51