Submission #73482

#	Time	Username	Problem	Language	Result	Execution time	Memory
73482		haitun	Global Warming (CEOI18_glo)	C++14	28 / 100	2067 ms	4604 KiB

glo

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25