oj.uz

Submission #859211

# Submission time Handle Problem Language Result Execution time Memory
859211 2023-10-10T01:30:23 Z chrispham258 Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 155716 KB 
/* Pham Ngoc Tho aka Chis Pham                           */
/* [Author : Pham Ngoc Tho] - THPT Chuyen Nguyen Du      */
/* [ 2024 - 12TH GO VOI 24 ] - From Nguyen Du with love  */

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define oo 0x3f
#define ff first
#define ss second
#define endl "\n"
#define ins insert
#define chis id<<1
#define pham (id<<1) + 1
#define sqr(x) ((x) * 1ll * (x))
#define gcd(a, b) __gcd(a, b)
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(),x.rend()
#define repu(i, x, n) for(int i = x; i <= n; ++i)
#define repd(i, n, x) for(int i = n; i >= x; --i)
#define reset(x, val) memset(x, val, sizeof(x))

typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

template<class T> bool getbit(T val, int i) { return (val >> i) & 1; }
template<class T> int cntbit(T val)        { return val == 0 ? 0 : cntbit(val >> 1) + (val & 1); }
template<class T> ll fpow(T a, const T b) { ll res = 1, x = a, y = b; while(y){if(y & 1)res *= x; x = x * x; y>>=1;}; return res; }
template<class T> ll modfpow(T a, T b, const T &m) { ll res = 1, x = a, y = b; x %= m; while(y){if(y & 1){res *= x; res %= m;}; x = x * x; x %= m; y >>= 1; } return res % m; }
template<class T> T lcm(T &a, T &b) { return a / gcd(a, b) * b; }

const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;

inline char gc() { static char buf[1 << 23]; static size_t bc, be; if(bc >= be){ buf[0] = 0, bc = 0; be = fread(buf, 1, sizeof(buf), stdin); } return buf[bc++]; }
ll readLL() { ll a, c; while ((a = gc()) < 20); if (a == '-') return -readLL(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; }
int readInt() { int a, c; while ((a = gc()) < 10); if (a == '-') return -readInt(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; }

mt19937 RND(time(nullptr));
ll rnd(ll l, ll r)
{
    assert(l <= r);ll L = l, R = r;
    ll aft = (L + RND() * 1LL % (R - L + 1));
    return aft;
}

#define TASK "name"
#define FILE "DEBUG"
void setIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
    if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
}

template<class T> T multi(const T &a, const T &b) { T res = (a*b)%mod; return res;}
template<class T> bool umax(T &a, T b) { if(a < b){ a = b; return 1;} else return 0;}
template<class T> bool umin(T &a, T b) { if(a > b){ a = b; return 1;} else return 0;}

const int NmX = 5e5 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int n;
ll a[NmX];

void read()
{
    cin >> n;
    repu(i, 1, n) cin >> a[i];
}

namespace sub2{
    const int N = 5e3 + 7;

    class IT{
        public:
            int it[4 * N];

            void build(int id, int l, int r){
                if(l == r){
                    it[id] = a[l];
                    return;
                }

                int mid = (l + r) >> 1;
                build(chis, l, mid);
                build(pham, mid + 1, r);
                it[id] = max(it[chis], it[pham]);
            }

            int get(int id, int l, int r, int u, int v){
                if(r < u || v < l) return -INF;
                if(u <= l && r <= v) return it[id];
                int mid = (l + r) >> 1;
                return max(get(chis, l, mid, u, v), get(pham, mid + 1, r, u, v));
            }
    }IT;

    ll f[N][N], fi[N][N];

    void solve(){
        IT.build(1, 1, n);

        repu(i, 1, n)
        {
            repu(j, i + 2, n)
            {
                int k = (i + j)/2;
                f[i][j] = a[i] + a[j] + IT.get(1, 1, n, i + 1, k);
                umax(f[i][j], f[i][j - 1]);
            }
        }

        repd(i, n, 1){
            repu(j, 1, n)
                umax(f[i - 1][j], f[i][j]);
        }        
        
        int q; cin >> q;
        while(q--){
            int u, v;
            cin >> u >> v;
            cout << f[u][v] << endl;
        }
    }
}
void process()
{
    sub2::solve();
}

main()
{
    setIO();
    int test = 1;
    // cin >> test;
    while(test--)
    {
        read();
        process();
    }

    cerr << "Time elapsed: " << (1.0 * clock()/CLOCKS_PER_SEC) * 1000 << "ms.\n";
    return 0;
}

Compilation message

jumps.cpp:142:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  142 | main()
      | ^~~~
jumps.cpp: In function 'void setIO()':
jumps.cpp:61:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:61:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:62:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:62:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4824 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4824 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1062 ms 155716 KB Output is correct
12 Correct 1055 ms 155460 KB Output is correct
13 Correct 1049 ms 155620 KB Output is correct
14 Correct 1058 ms 155624 KB Output is correct
15 Correct 1049 ms 155612 KB Output is correct
16 Correct 1052 ms 155096 KB Output is correct
17 Correct 1055 ms 155104 KB Output is correct
18 Correct 1058 ms 155004 KB Output is correct
19 Correct 1056 ms 155596 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4824 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 1062 ms 155716 KB Output is correct
12 Correct 1055 ms 155460 KB Output is correct
13 Correct 1049 ms 155620 KB Output is correct
14 Correct 1058 ms 155624 KB Output is correct
15 Correct 1049 ms 155612 KB Output is correct
16 Correct 1052 ms 155096 KB Output is correct
17 Correct 1055 ms 155104 KB Output is correct
18 Correct 1058 ms 155004 KB Output is correct
19 Correct 1056 ms 155596 KB Output is correct
20 Execution timed out 4035 ms 19980 KB Time limit exceeded
21 Halted 0 ms 0 KB -