Submission #394769

#	Time	Username	Problem	Language	Result	Execution time	Memory
394769		juggernaut	Split the sequence (APIO14_sequence)	C++14	0 / 100	57 ms	2108 KiB

sequence

#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
//using namespace __gnu_pbds;
typedef long long ll;
//template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>void umin(T &a,T b){if(b<a)a=b;}
template<class T>void umax(T &a,T b){if(a<b)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n,k,a[100005];
ll pref[100005];
bool en[100005];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),pref[i]=pref[i-1]+a[i];
    en[n]=true;
    ll ans=0;
    vector<int>v;
    while(k--){
        ll mx=-1;
        int id;
        int last=1;
        for(int i=1;i<=n;i++)
            if(en[i]){
                ll sum=pref[i]-pref[last-1];
                ll prf=0;
                for(int j=last;j<i;j++){
                    prf+=a[j];
                    sum-=a[j];
                    if(prf*sum>mx){
                        mx=prf*sum;
                        id=j;
                    }
                }
                last=i+1;
            }
        ans+=mx;
        en[id]=true;
        v.push_back(id);
    }
    printf("%lld\n",ans);
    for(int x:v)printf("%d ",x);
}

Compilation message (stderr)

sequence.cpp: In function 'void usaco(std::string)':
sequence.cpp:6:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:6:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:22:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]),pref[i]=pref[i-1]+a[i];
      |                          ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29