oj.uz

Submission #724656

# Submission time Handle Problem Language Result Execution time Memory
724656 2023-04-15T17:16:41 Z TimDee Homecoming (BOI18_homecoming) C++17
31 / 100
 689 ms 262144 KB 
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\

#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using ll = long long;
#define int long long
//#define double long double
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 998244353;

struct sgt {
    vector<int> t,lazy;
    int sz;
    void push(int v) {
        t[v]+=lazy[v];
        if (2*v+1<2*sz-1) lazy[2*v+1]+=lazy[v];
        if (2*v+2<2*sz-1) lazy[2*v+2]+=lazy[v];
        lazy[v]=0;
    }
    sgt(int n) {
        sz=1; while (sz<n) sz<<=1;
        t.assign(2*sz-1,0);
        lazy.assign(2*sz-1,0);
    }
    int query(int v, int l, int r, int lx, int rx) {
        if (lazy[v]) push(v);
        if (rx<=l || r<=lx) return -inf;
        if (lx<=l && r<=rx) {
            return t[v];
        }
        int m=(l+r)>>1;
        return max(query(2*v+1,l,m,lx,rx),query(2*v+2,m,r,lx,rx));
    }
    int query(int l, int r) {
        return query(0,0,sz,l,r);
    }
    void add(int v, int l, int r, int lx, int rx, int x) {
        if (lazy[v]) push(v);
        if (rx<=l || r<=lx) return;
        if (lx<=l && r<=rx) {
            lazy[v]+=x;
            push(v);
            return;
        }
        int m=(l+r)>>1;
        add(2*v+1,l,m,lx,rx,x);
        add(2*v+2,m,r,lx,rx,x);
        t[v]=max(t[2*v+1],t[2*v+2]);
    }
    void add(int l, int r, int x) {
        add(0,0,sz,l,r,x);
    }
};

#undef int

long long solve(int N, int K, int *A, int *B) {
    #define int long long
    const int inf = 1e18;

    int ans=0;
    int n=N, k=K;
    vector<int> a,b;
    forn(i,n) a.pb(A[i]); forn(i,n) a.pb(a[i]);
    forn(i,n) b.pb(B[i]); forn(i,n) b.pb(b[i]); forn(i,n) b.pb(b[i]);
    vector<int> pra(2*n+1,0), prb(3*n+1,0);
    forn(i,2*n) pra[i+1]=pra[i]+a[i];
    forn(i,3*n) prb[i+1]=prb[i]+b[i];
    vector<int> dp(2*n+1,0);

    sgt st(2*n+1);

    for (int i=1; i<=2*n; ++i) {
        dp[i]=max(dp[i],dp[i-1]);
        int sub=(i>=n)?dp[i-n]:0;
        int l=max(0ll,i-n);
        int r=i;
        int x=st.query(l,r);
        dp[i] = max(dp[i],x+a[i-1]-(prb[i+k-1]-prb[i-1])-sub);
        st.add(i,i+1,dp[i]);
        st.add(0,i,a[i-1]-b[i-1]);
        if (n<=5000) if (i+k-1>=n) st.add(0,i+k-n,b[i+k-1-n]);
    }
    return dp[2*n];

    #undef int
}

Compilation message

homecoming.cpp:5:1: warning: multi-line comment [-Wcomment]
    5 | //   \ __ __  \
      | ^
homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:79:15: warning: unused variable 'inf' [-Wunused-variable]
   79 |     const int inf = 1e18;
      |               ^~~
homecoming.cpp:81:9: warning: unused variable 'ans' [-Wunused-variable]
   81 |     int ans=0;
      |         ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1364 KB Output is correct
7 Correct 7 ms 1364 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 3 ms 340 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 84072 KB Output is correct
2 Correct 30 ms 924 KB Output is correct
3 Runtime error 270 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 8 ms 1364 KB Output is correct
7 Correct 7 ms 1364 KB Output is correct
8 Correct 6 ms 672 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 689 ms 84072 KB Output is correct
12 Correct 30 ms 924 KB Output is correct
13 Runtime error 270 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -