oj.uz

Submission #73482

# Submission time Handle Problem Language Result Execution time Memory
73482 2018-08-28T10:16:46 Z haitun Global Warming (CEOI18_glo) C++14
28 / 100
 2000 ms 4604 KB 
#include <bits/stdc++.h>
#include <bits/stdc++.h>
//#include "functions.h"
#define FOR(x,y) for(int x = 0; x < y; x++)
#define ALLR(x) x.begin(),x.end()
#define con continue
#define ll long long
#define LINF LLONG_MAX
#define INF INT_MAX
#define pii pair<int,int>
#define vi vector <int>
#define pb push_back
#define F first
#define S second
#define len(x) x.length()
#define sz(x) x.size()
using namespace std;
// Binary search
int GetCeilIndex(vi arr, vector<int> &T, int l, int r,
                 int key)
{
    while (r - l > 1)
    {
        int m = l + (r - l)/2;
        if (arr[T[m]] >= key)
            r = m;
        else
            l = m;
    }
 
    return r;
}
 
int LongestIncreasingSubsequenceLength(vi arr)
{
    int n = arr.size();
    // Add boundary case, when array n is zero
    // Depend on smart pointers
 
    vector<int> tailIndices(n, 0); // Initialized with 0 
    vector<int> prevIndices(n, -1); // initialized with -1
 
    int len = 1; // it will always point to empty location
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[tailIndices[0]])
        {
            // new smallest value
            tailIndices[0] = i;
        }
        else if (arr[i] > arr[tailIndices[len-1]])
        {
            // arr[i] wants to extend largest subsequence
            prevIndices[i] = tailIndices[len-1];
            tailIndices[len++] = i;
        }
        else
        {
            // arr[i] wants to be a potential condidate of
            // future subsequence
            // It will replace ceil value in tailIndices
            int pos = GetCeilIndex(arr, tailIndices, -1,
                                   len-1, arr[i]);
 
            prevIndices[i] = tailIndices[pos-1];
            tailIndices[pos] = i;
        }
    }
 
    //cout << "LIS of given input" << endl;
    //for (int i = tailIndices[len-1]; i >= 0; i = prevIndices[i])cout << arr[i] << " ";cout << endl;
 
    return len;
}
 
int main() {
    int n, b;
    cin >> n >> b;
    vi t(n);
    FOR(j, n)   cin >> t[j];
    
    if(b == 0)
    {
        cout << LongestIncreasingSubsequenceLength(t);
        return 0;
    }
    
    int ans = LongestIncreasingSubsequenceLength(t);

    for(int k = -b; k <= b; k++)
    {
        if(k == 1 - b)   k = b;
        vi temp = t;
        FOR(i, n)
        {
            FOR(q,i)    temp[q] += k;
            ans = max(ans, LongestIncreasingSubsequenceLength(temp));
                
            temp = t;
                
            for(int q = n - 1; q > i; q--)  temp[q] += k;
            ans = max(ans, LongestIncreasingSubsequenceLength(temp));
        }
    }
    
    cout << ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 536 KB Output is correct
11 Correct 3 ms 568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 536 KB Output is correct
11 Correct 3 ms 568 KB Output is correct
12 Correct 3 ms 568 KB Output is correct
13 Correct 3 ms 568 KB Output is correct
14 Correct 3 ms 568 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 624 KB Output is correct
17 Correct 2 ms 624 KB Output is correct
18 Correct 2 ms 624 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 536 KB Output is correct
11 Correct 3 ms 568 KB Output is correct
12 Correct 3 ms 568 KB Output is correct
13 Correct 3 ms 568 KB Output is correct
14 Correct 3 ms 568 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 624 KB Output is correct
17 Correct 2 ms 624 KB Output is correct
18 Correct 2 ms 624 KB Output is correct
19 Correct 782 ms 748 KB Output is correct
20 Correct 961 ms 748 KB Output is correct
21 Correct 840 ms 748 KB Output is correct
22 Correct 3 ms 748 KB Output is correct
23 Correct 601 ms 748 KB Output is correct
24 Correct 592 ms 868 KB Output is correct
25 Correct 238 ms 868 KB Output is correct
26 Correct 496 ms 868 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 4604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 4604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 4604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 436 KB Output is correct
6 Correct 2 ms 436 KB Output is correct
7 Correct 3 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 2 ms 536 KB Output is correct
11 Correct 3 ms 568 KB Output is correct
12 Correct 3 ms 568 KB Output is correct
13 Correct 3 ms 568 KB Output is correct
14 Correct 3 ms 568 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 624 KB Output is correct
17 Correct 2 ms 624 KB Output is correct
18 Correct 2 ms 624 KB Output is correct
19 Correct 782 ms 748 KB Output is correct
20 Correct 961 ms 748 KB Output is correct
21 Correct 840 ms 748 KB Output is correct
22 Correct 3 ms 748 KB Output is correct
23 Correct 601 ms 748 KB Output is correct
24 Correct 592 ms 868 KB Output is correct
25 Correct 238 ms 868 KB Output is correct
26 Correct 496 ms 868 KB Output is correct
27 Execution timed out 2059 ms 4604 KB Time limit exceeded
28 Halted 0 ms 0 KB -