Submission #896466

#	Time	Username	Problem	Language	Result	Execution time	Memory
896466		Alcabel	Žarulje (COI15_zarulje)	C++17	22 / 100	299 ms	524288 KiB

zarulje

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

const int mod = 1e9 + 7;

struct Modint {
    int x;
    Modint() {
        x = 0;
    }
    Modint(int _x) {
        while (_x >= mod) {
            _x -= mod;
        }
        while (_x < 0) {
            _x += mod;
        }
        x = _x;
    }
    Modint(long long _x) {
        if (_x >= mod || _x <= -mod) {
            _x %= mod;
        }
        if (_x < 0) {
            _x += mod;
        }
        x = _x;
    }
    Modint operator+(const Modint& other) const {
        return Modint(x + other.x);
    }
    Modint operator*(const Modint& other) const {
        return Modint(x * 1ll * other.x);
    }
    void operator+=(const Modint& other) {
        *this = *this + other;
    }
    void operator*=(const Modint& other) {
        *this = *this * other;
    }
    Modint operator^(long long p) const {
        Modint res = 1, tmp = x;
        while (p > 0) {
            if (p & 1) {
                res *= tmp;
            }
            tmp *= tmp;
            p >>= 1;
        }
        return res;
    }
    Modint operator/(const Modint& other) const {
        return *this * (other ^ (mod - 2));
    }
    void operator/=(const Modint& other) {
        *this = *this / other;
    }
    ~Modint() {}
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<vector<Modint>> dp(n + 1, vector<Modint>(n + 1));
    dp[0][n] = 1;
    for (int len = n - 1; len >= 1; --len) {
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len;
            if (l == 0) {
                dp[l][r] = dp[l][r + 1];
            } else if (r == n) {
                dp[l][r] = dp[l - 1][r];
            } else {
                if (a[l - 1] > a[r]) {
                    dp[l][r] = dp[l - 1][r];
                } else if (a[l - 1] < a[r]) {
                    dp[l][r] = dp[l][r + 1];
                } else {
                    dp[l][r] = dp[l - 1][r] + dp[l][r + 1];
                }
            }
        }
    }
    while (k--) {
        int pos;
        cin >> pos;
        --pos;
        cout << dp[pos][pos + 1].x << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCALa
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 38
• Subtask 3: 0 / 40