Submission #161071

#	Time	Username	Problem	Language	Result	Execution time	Memory
161071		stoyan_malinin	Bigger segments (IZhO19_segments)	C++14	0 / 100	9 ms	508 KiB

segments

#include<iostream>
#include<vector>

using namespace std;

const int MAXN = 5e5 + 5;

int n;
long long a[MAXN];

struct segment
{
    int l, r;
    long long sum;

    segment(){}
    segment(int l, int r, long long sum)
    {
        this->l = l;
        this->r = r;
        this->sum = sum;
    }
};

vector <segment> v;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int answer = 0;

    cin >> n;
    for(int i = 0;i<n;i++)
    {
        cin >> a[i];
    }

    v.push_back(segment(0, 0, a[0]));

    segment curr = segment(1, 0, 0);
    for(int i = 1;i<n;i++)
    {
        curr.r++;
        curr.sum += a[i];

        if(curr.sum >= v.back().sum)
        {
            v.push_back(curr);
            curr = segment(i+1, i, 0);
        }

        for(int j = v.size()-1;j>=1;j--)
        {
            while(v[j].sum - a[ v[j].l ] >= v[j-1].sum + a[ v[j].l ])
            {
                v[j].sum -= a[ v[j].l ];
                v[j-1].sum -= a[ v[j].l ];

                v[j].l++;
                v[j-1].r++;
            }
        }
    }

    cout << v.size() << '\n';
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:32:9: warning: unused variable 'answer' [-Wunused-variable]
     int answer = 0;
         ^~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27