oj.uz

Submission #859244

# Submission time Handle Problem Language Result Execution time Memory
859244 2023-10-10T02:16:16 Z wii Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 161408 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;

#define int ll
typedef pair<int, int> pii;

#define X first
#define Y second
#define gcd __gcd
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define bit(i, mask) ((mask) >> (i) & 1)
#define reset(x, val) memset(x, val, sizeof(x))
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)
#define FastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

const ll Linf = 0x3f3f3f3f3f3f3f3f;
const int Inf = 0x3f3f3f3f;
const ll Mod = 1e9 + 7;
const ll Mod2 = ll(1e9) + 9;
const int Lim = 1e6 + 5;
const int inv6 = 166666668;

#define Sieve
#ifdef Sieve
    vector<int> pr;
    vector<int> lpf;
    void Linear_sieve(int n = Lim) {
        pr.assign(1, 2);
        lpf.assign(n + 1, 2);

        for (int x = 3; x <= n; x += 2) {
            if (lpf[x] == 2) pr.push_back(lpf[x] = x);
            for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
                lpf[pr[i] * x] = pr[i];
        }
    }
#endif

// #define Ckn_calc
#ifdef Ckn_calc
    const int LIM = 1e6 + 16;

    int fact[LIM + 10]; /// factorial:         fact[n] = n!
    int invs[LIM + 10]; /// inverse modular:   invs[n] = n^(-1)
    int tcaf[LIM + 10]; /// inverse factorial: tcaf[n] = (n!)^(-1)
    void precal_nck(int n = LIM)
    {
        fact[0] = fact[1] = 1;
        invs[0] = invs[1] = 1;
        tcaf[0] = tcaf[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            fact[i] = (1LL * fact[i - 1] * i) % Mod;
            invs[i] = Mod - 1LL * (Mod / i) * invs[Mod % i] % Mod;
            tcaf[i] = (1LL * tcaf[i - 1] * invs[i]) % Mod;
        }
    }

    ll C(int n, int k) {
        if (n < k || k < 0) return 0;

        ll res = fact[n];
        res *= tcaf[k], res %= Mod;
        res *= tcaf[n - k], res %= Mod;
        return res;
    }

    ll P(int n, int k) {
        ll res = fact[n];
        res *= tcaf[n - k], res %= Mod;
        return res;
    }
#endif

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

const int base = 3;
const int N = 5e3 + 5;
const int K = log2(N) + 2;
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};
const int block_size = sqrt(2e9) + 2;

int f[N][N];
int n, a[N];

void solve() {
    cin >> n;
    foru(i, 1, n) cin >> a[i];

    foru(l, 1, n) {
        int mid = l + 1, u = a[l + 1];
        foru(r, l + 2, n) {
            while ((mid + 1) * 2 <= l + r)
                maximize(u, a[++mid]);
            f[l][r] = a[l] + u + a[r];
        }
    }

    ford(l, n, 1) {
        foru(r, l + 1, n) {
            maximize(f[l][r], f[l + 1][r]);
            maximize(f[l][r], f[l][r - 1]);
        }
    }

    int q; cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;

        cout << f[l][r] << "\n";
    }
}

signed main() {
    FastIO;

    #define task "test"
    if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

    #ifdef Sieve
        Linear_sieve();
    #endif

    #ifdef Ckn_calc
        precal_nck();
    #endif

    int ntest = 1;
    // cin >> ntest;
    while (ntest--) {
        //cout << "Case " << q << ": " << "\n"; 
        solve();
        cout << "\n";
    }

    return 0;
}

/**  /\_/\
 *  (= ._.)
 *  / >TL \>AC
**/

Compilation message

jumps.cpp: In function 'void Linear_sieve(ll)':
jumps.cpp:45:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for (int i = 1; i < pr.size() && pr[i] <= lpf[x] && pr[i] * x <= n; ++i)
      |                             ~~^~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:133:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:134:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9436 KB Output is correct
2 Correct 5 ms 13016 KB Output is correct
3 Correct 6 ms 13012 KB Output is correct
4 Correct 6 ms 13012 KB Output is correct
5 Correct 7 ms 13040 KB Output is correct
6 Correct 6 ms 13016 KB Output is correct
7 Correct 5 ms 13016 KB Output is correct
8 Correct 6 ms 13100 KB Output is correct
9 Correct 6 ms 13016 KB Output is correct
10 Correct 7 ms 13016 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9436 KB Output is correct
2 Correct 5 ms 13016 KB Output is correct
3 Correct 6 ms 13012 KB Output is correct
4 Correct 6 ms 13012 KB Output is correct
5 Correct 7 ms 13040 KB Output is correct
6 Correct 6 ms 13016 KB Output is correct
7 Correct 5 ms 13016 KB Output is correct
8 Correct 6 ms 13100 KB Output is correct
9 Correct 6 ms 13016 KB Output is correct
10 Correct 7 ms 13016 KB Output is correct
11 Correct 191 ms 160464 KB Output is correct
12 Correct 200 ms 160208 KB Output is correct
13 Correct 201 ms 160300 KB Output is correct
14 Correct 190 ms 159372 KB Output is correct
15 Correct 189 ms 160340 KB Output is correct
16 Correct 190 ms 158716 KB Output is correct
17 Correct 190 ms 160720 KB Output is correct
18 Correct 194 ms 158448 KB Output is correct
19 Correct 197 ms 161408 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9436 KB Output is correct
2 Correct 5 ms 13016 KB Output is correct
3 Correct 6 ms 13012 KB Output is correct
4 Correct 6 ms 13012 KB Output is correct
5 Correct 7 ms 13040 KB Output is correct
6 Correct 6 ms 13016 KB Output is correct
7 Correct 5 ms 13016 KB Output is correct
8 Correct 6 ms 13100 KB Output is correct
9 Correct 6 ms 13016 KB Output is correct
10 Correct 7 ms 13016 KB Output is correct
11 Correct 191 ms 160464 KB Output is correct
12 Correct 200 ms 160208 KB Output is correct
13 Correct 201 ms 160300 KB Output is correct
14 Correct 190 ms 159372 KB Output is correct
15 Correct 189 ms 160340 KB Output is correct
16 Correct 190 ms 158716 KB Output is correct
17 Correct 190 ms 160720 KB Output is correct
18 Correct 194 ms 158448 KB Output is correct
19 Correct 197 ms 161408 KB Output is correct
20 Execution timed out 4017 ms 83084 KB Time limit exceeded
21 Halted 0 ms 0 KB -