Submission #1022056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022056		vinh1e2kg	Zoltan (COCI16_zoltan)	C++14	21 / 140	1091 ms	3412 KiB

zoltan

#include<bits/stdc++.h>
#define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout);
#define TaZinh "test"
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define PB push_back
#define ll long long
#define pii pair<int, int>
#define SZ(a) (int)(a.size())
#define ALL(a) a.begin(), a.end()
#define MS(a, v) memset(a, v, sizeof a)
#define REP(i, n) for(int i = 0; i < (n); ++ i)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FOD(i, a, b) for(int i = (a); i >= (b); -- i)

template<class X, class Y>
        bool maximize(X &x, const Y & y){
                if(x < y){
                        x = y;
                        return true;
                }
                else return false;
        }


template<class X, class Y>
        bool minimize(X &x, const Y & y){
                if(x > y){
                        x = y;
                        return true;
                }
                else return false;
        }

const int N = 200005;
const int mod = 1e9 + 7;

int n, a[N], f1[N], g1[N], f2[N], g2[N];
int up1[N], up2[N], dw1[N], dw2[N];

int Pow(int a, int b){
            int res = 1;
            while(b > 0){
                    if(b & 1) res = 1ll * res * a % mod;
                    a = 1ll * a * a % mod; b >>= 1;
            }
            return res;
}

void add(int &a, int b){
        a += b;
        if(a >= mod) a -= mod;
}

int main(){

        ios_base :: sync_with_stdio(0); 
        cin.tie(0); cout.tie(0); 

        if(fopen(TaZinh".inp", "r"))
                TSun(TaZinh);

        cin >> n;
        FOR(i, 1, n) cin >> a[i];

        FOR(i, 1, n){
                f1[i] = f2[i] = up1[i] = up2[i] = 1;
                FOR(j, 1, i - 1){
                        if(a[j] < a[i]){
                                if(maximize(f1[i], f1[j] + 1))
                                        up1[i] = up1[j];
                                else if(f1[i] == f1[j] + 1)
                                        add(up1[i], up1[j]);
                        }
                                
                        if(a[j] > a[i]){
                                if(maximize(f2[i], f2[j] + 1))
                                        up1[i] = up1[j];
                                else if(f2[i] == f2[j] + 1)
                                        add(up1[i], up1[j]);
                        }
                                
                } 
        }

        int len = 0;

        FOD(i, n, 1){
                g1[i] = g2[i] = dw1[i] = dw2[i] = 1;
                FOR(j, i + 1, n){
                        if(a[j] > a[i]){
                                if(maximize(g2[i], g2[j] + 1))
                                        dw2[i] = dw2[j];
                                else if(g2[i] == g2[j] + 1)
                                        add(dw2[i], dw2[j]);
                        }
                                
                        if(a[j] < a[i]){
                                if(maximize(g1[i], g1[j] + 1))
                                        dw1[i] = dw1[j];
                                else if(g1[i] == g1[j] + 1)
                                        add(dw1[i], dw1[j]);
                        }   
                                    
                } 
                maximize(len, f1[i] + g1[i] - 1);
                maximize(len, f2[i] + g2[i] - 1);
        }

        int cnt = 0;

        FOR(i, 1, n){
                // if(f1[i] + g1[i] == len + 1)
                //         add(cnt, 1ll * up1[i] * dw1[i] % mod);
                if(g1[i] + g2[i] == len + 1)
                        add(cnt, 1ll * dw1[i] * dw2[i] % mod);
        }

        cout << len << " " << 1ll * cnt * Pow(2, n - len) % mod;

        return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:2:25: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout);
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:64:17: note: in expansion of macro 'TSun'
   64 |                 TSun(TaZinh);
      |                 ^~~~
zoltan.cpp:2:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define TSun(TZ) freopen(TZ".inp", "r", stdin), freopen(TZ".out", "w", stdout);
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:64:17: note: in expansion of macro 'TSun'
   64 |                 TSun(TaZinh);
      |                 ^~~~

• Subtask 1: 21 / 140