Submission #520281

#	Time	Username	Problem	Language	Result	Execution time	Memory
520281		krit3379	Split the sequence (APIO14_sequence)	C++14	0 / 100	77 ms	7136 KiB

sequence

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

struct A{
    long long a,b,c;
    bool operator<(const A& o)const{
        return c>o.c;
    }
};

long long val[N],l[N],r[N],qs[N],a,b,c,ans;
int p[N];
priority_queue<A> q;

int fp(int v){return (v==p[v])?v:p[v]=fp(p[v]);}

int main(){
    int n,k,i,j,st;
    scanf("%d %d",&n,&k);
    st=n;
    iota(p,p+n+1,0);
    for(i=1;i<=n;i++)scanf("%lld",&val[i]),qs[i]=qs[i-1]+val[i],ans+=val[i]*qs[i-1],l[i]=r[i]=i;
    for(i=1;i<n;i++)q.push({i,i+1,val[i]*val[i+1]});
    while(st!=k+1){
        a=q.top().a;
        b=q.top().b;
        c=q.top().c;
        q.pop();
        if(val[fp(a)]*val[fp(b)]!=c)continue;
        val[fp(a)]+=val[fp(b)];
        l[fp(a)]=min(l[fp(a)],l[fp(b)]);
        r[fp(a)]=max(r[fp(a)],r[fp(b)]);
        p[fp(b)]=fp(a);
        if(r[fp(a)]!=1)q.push({fp(a),fp(l[fp(a)]-1),val[fp(a)]*val[fp(l[fp(a)]-1)]});
        if(r[fp(a)]!=n)q.push({fp(a),fp(r[fp(a)]+1),val[fp(a)]*val[fp(r[fp(a)]+1)]});
        ans-=c;
        st--;
    }
    printf("%lld\n",ans);
    for(i=1;r[fp(i)]<n;i++){
        printf("%d ",r[fp(i)]);
        i=r[fp(i)];
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:42:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   42 |         printf("%d ",r[fp(i)]);
      |                 ~^   ~~~~~~~~
      |                  |          |
      |                  int        long long int
      |                 %lld
sequence.cpp:19:15: warning: unused variable 'j' [-Wunused-variable]
   19 |     int n,k,i,j,st;
      |               ^
sequence.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:23:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     for(i=1;i<=n;i++)scanf("%lld",&val[i]),qs[i]=qs[i-1]+val[i],ans+=val[i]*qs[i-1],l[i]=r[i]=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