oj.uz

Submission #161081

# Submission time Handle Problem Language Result Execution time Memory
161081 2019-10-31T13:36:37 Z stoyan_malinin Bigger segments (IZhO19_segments) C++14
13 / 100
 1500 ms 376 KB 
#include<iostream>
#include<vector>
#include<random>

using namespace std;

const int MAXN = 5e5 + 5;

mt19937 rnd(69420);

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 mySolve()
{
    v.clear();

    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];

        bool update = true;
        while(update==true)
        {
            update = false;
            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 ])
                {
                    update = true;

                    v[j].sum -= a[ v[j].l ];
                    v[j-1].sum += a[ v[j].l ];

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

                    v[j].sum -= a[ v[j].l ];
                    v[j-1].sum += a[ v[j].l ];

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


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

    return v.size();
}

int rec(int index, int lastSum, int currSum, int cnt)
{
    if(index==n) return cnt;

    int ans = 0;
    ans = rec(index+1, lastSum, currSum+a[index], cnt);

    if(currSum+a[index]>=lastSum)
    {
        ans = max(ans, rec(index+1, currSum+a[index], 0, cnt+1));
    }

    return ans;
}

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];
    }

    cout << rec(0, 0, 0, 0) << '\n';
    return 0;

    while(true)
    {
        n = 1 + rnd()%20;
        for(int i = 0;i<n;i++)
        {
            a[i] = rnd();
        }

        int ans1 = mySolve();
        int ans2 = rec(0, 0, 0, 0);

        if(ans1!=ans2)
        {
            cout << "FAK" << '\n';
            //for()
        }
    }
}
/*
5
6 2 3 9 13
*/

Compilation message

segments.cpp: In function 'int mySolve()':
segments.cpp:57:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 1;j<v.size();j++)
                           ~^~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:103:9: warning: unused variable 'answer' [-Wunused-variable]
     int answer = 0;
         ^~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 248 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 248 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Execution timed out 1544 ms 376 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 248 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Execution timed out 1544 ms 376 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 248 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Execution timed out 1544 ms 376 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 248 KB Output is correct
16 Correct 4 ms 376 KB Output is correct
17 Execution timed out 1544 ms 376 KB Time limit exceeded
18 Halted 0 ms 0 KB -