Submission #210151

#	Time	Username	Problem	Language	Result	Execution time	Memory
210151		stefdasca	Zoltan (COCI16_zoltan)	C++14	21 / 140	1100 ms	22520 KiB

zoltan

#include<bits/stdc++.h>
using namespace std;

int n, v[200002], sortt[200002];
map<int, int> mp;
int dp[1002][1002];
int cnt[1002][1002];

const int mod = 1000000007;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        sortt[i] = v[i];
    }
    sort(sortt + 1, sortt + n + 1);
    int valdis = 0;
    for(int i = 1; i <= n; ++i)
        if(i == 1 || sortt[i] > sortt[i-1])
            mp[sortt[i]] = ++valdis;
    for(int i = 1; i <= n; ++i)
        v[i] = mp[v[i]];
    dp[v[1]][v[1]] = cnt[v[1]][v[1]] = 1;
    int put = 1;
    bool ok = 1;
    for(int i = 2; i <= n; ++i)
    {
        for(int j = 1; j <= valdis; ++j)
            for(int k = valdis; k >= j; --k)
            {
                if(!dp[j][k])
                    continue;
                /*
                if(j <= v[i] && v[i] <= k)
                {
                    cnt[j][k] = (cnt[j][k] + cnt[j][k]);
                    if(cnt[j][k] >= mod)
                        cnt[j][k] -= mod;
                }
                else
                {
                */
                if(v[i] < j)
                {
                    if(dp[j][k] + 1 > dp[v[i]][k])
                    {
                        dp[v[i]][k] = dp[j][k] + 1;
                        cnt[v[i]][k] = cnt[j][k];
                    }
                    else if(dp[j][k] + 1 == dp[v[i]][k])
                    {
                        cnt[v[i]][k] = (cnt[v[i]][k] + cnt[j][k]);
                        if(cnt[v[i]][k] >= mod)
                            cnt[v[i]][k] -= mod;
                    }
                }
                if(v[i] > k)
                {
                    if(dp[j][k] + 1 > dp[j][v[i]])
                    {
                        dp[j][v[i]] = dp[j][k] + 1;
                        cnt[j][v[i]] = cnt[j][k];
                    }
                    else if(dp[j][k] + 1 == dp[j][v[i]])
                    {
                        cnt[j][v[i]] = (cnt[j][v[i]] + cnt[j][k]);
                        if(cnt[j][v[i]] >= mod)
                            cnt[j][v[i]] -= mod;
                    }
                }
                //   }
            }
        if(v[i] != v[i-1])
            ok = 0;
        if(ok)
        {
            put = put + put;
            if(put >= mod)
                put -= mod;
            dp[v[i]][v[i]] = 1;
            cnt[v[i]][v[i]] = cnt[v[i]][v[i]] + cnt[v[i]][v[i]];
            if(cnt[v[i]][v[i]] >= mod)
                cnt[v[i]][v[i]] -= mod;
            cnt[v[i]][v[i]] += put;
            if(cnt[v[i]][v[i]] >= mod)
                cnt[v[i]][v[i]] -= mod;
        }
        else
        {
            dp[v[i]][v[i]] = 1;
            cnt[v[i]][v[i]] += put;
            if(cnt[v[i]][v[i]] >= mod)
                cnt[v[i]][v[i]] -= mod;
        }
        //  cout << dp[1][2] << " " << cnt[1][2] << '\n';
        //  cout << dp[1][3] << " " << cnt[1][3] << '\n';
        for(int j = 1; j <= valdis; ++j)
        {
            int maxv = 0;
            for(int k = j; k <= valdis; ++k)
                if(dp[j][k] < maxv)
                    dp[j][k] = cnt[j][k] = 0;
                else
                    maxv = dp[j][k];
        }
    }
    int bst = 0;
    int nr = 0;
    for(int i = 1; i <= valdis; ++i)
        for(int j = i; j <= valdis; ++j)
            if(dp[i][j] > bst)
            {
                bst = dp[i][j];
                nr = cnt[i][j];
            }
            else if(dp[i][j] == bst)
            {
                nr = nr + cnt[i][j];
                if(nr >= mod)
                    nr -= mod;
            }
    cout << bst << " " << nr << '\n';
    return 0;
}

• Subtask 1: 21 / 140