oj.uz

답안 #90546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90546 2018-12-22T10:54:15 Z 314rate 수열 (APIO14_sequence) C++14
0 / 100
 8 ms 1512 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=100000+5;

ll n,k,pre[N];

ll s(ll st,ll dr)
{
    return pre[dr]-pre[st-1];
}

struct info
{
    ll st;
    ll dr;
    ll val;
    ll p;
};

pair<ll,ll>split(ll st,ll dr)
{
    if(st==dr)
    {
        return {-1,-1};
    }
    ll a=0LL;
    ll id;
    for(ll p=st;p<dr;p++)
    {
        ll X=s(st,p);
        ll Y=s(p+1,dr);
        ll pr=X*Y;
        a=max(a,pr);
        if(a==pr)
        {
            id=p;
        }
    }
    return {a,id};
}

vector<info>cur;

void add(ll st,ll dr)
{
    pair<ll,ll>aux=split(st,dr);
    cur.push_back({st,dr,aux.first,aux.second});
}

void del(ll p)
{
    for(ll i=p;i+1<cur.size();i++)
    {
        cur[i]=cur[i+1];
    }
    cur.pop_back();
}

vector<ll>who;

void print()
{
    cout<<"GAYYY::\n\n";
    for(auto &x:cur)
    {
        cout<<x.st<<" "<<x.dr<<" : "<<x.val<<"\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
    {
        ll x;
        cin>>x;
        pre[i]=x+pre[i-1];
    }
    add(1,n);
    ll ans=0LL;
   // print();
    for(ll va=1;va<=k;va++)
    {
        ll mx=0LL;
        ll id;
        for(ll i=0;i<cur.size();i++)
        {
            mx=max(mx,cur[i].val);
            if(mx==cur[i].val)
            {
                id=i;
            }
        }
        ll st=cur[id].st;
        ll dr=cur[id].dr;
        ll p=cur[id].p;
        ans+=mx;
        del(id);
       /// cout<<st<<" "<<dr<<" : "<<p<<"\n";
        add(st,p);
        add(p+1,dr);
      //  print();
      who.push_back(p);
    }
    cout<<ans<<"\n";
    for(auto &x:who)
    {
        cout<<x<<" ";
    }
    cout<<"\n";
    return 0;
}
/**

7 3
4 1 3 4 0 2 3

**/

Compilation message

sequence.cpp: In function 'void del(ll)':
sequence.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(ll i=p;i+1<cur.size();i++)
                ~~~^~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:91:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0;i<cur.size();i++)
                    ~^~~~~~~~~~~
sequence.cpp: In function 'std::pair<long long int, long long int> split(ll, ll)':
sequence.cpp:43:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return {a,id};
                 ^
sequence.cpp: In function 'int main()':
sequence.cpp:99:21: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ll st=cur[id].st;
                     ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB contestant found the optimal answer: 108 == 108
2 Incorrect 2 ms 508 KB contestant didn't find the optimal answer: 951 < 999
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 508 KB contestant didn't find the optimal answer: 1093726 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 508 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 2 ms 508 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 2 ms 508 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 2 ms 540 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 2 ms 836 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 2 ms 836 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 2 ms 836 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Incorrect 2 ms 836 KB contestant didn't find the optimal answer: 193235243 < 193556962
9 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 836 KB contestant didn't find the optimal answer: 21419072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 836 KB contestant didn't find the optimal answer: 1794250000 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1512 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Incorrect 8 ms 1512 KB contestant didn't find the optimal answer: 19874432171 < 19874432173
3 Halted 0 ms 0 KB -