oj.uz

Submission #724607

# Submission time Handle Problem Language Result Execution time Memory
724607 2023-04-15T16:23:23 Z TimDee Homecoming (BOI18_homecoming) C++17
31 / 100
 930 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];
        lazy[2*v+1]+=lazy[v];
        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(4*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;
        int lq=query(2*v+1,l,m,lx,rx);
        int rq=query(2*v+2,m,r,lx,rx);
        t[v]=max(t[2*v+1],t[2*v+2]);
        return max(lq,rq);
    }
    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);
        //cout<<l<<' '<<r<<' '<<x<<": "<<a[i-1]<<' '<<(prb[i+k-1]-prb[i-1])<<'\n';
        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 (i+k-1>=n) st.add(0,i+k-n,b[i+k-1-n]);
        //for(auto&x:st.t) cout<<x<<' '; cout<<'\n';
        //for(auto&x:st.lazy) cout<<x<<' '; cout<<'\n';
        //forn(j,i+1) cout<<st.query(j,j+1)<<' '; cout<<'\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:82:15: warning: unused variable 'inf' [-Wunused-variable]
   82 |     const int inf = 1e18;
      |               ^~~
homecoming.cpp:84:9: warning: unused variable 'ans' [-Wunused-variable]
   84 |     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 1620 KB Output is correct
7 Correct 8 ms 1520 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 8 ms 1620 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 930 ms 100492 KB Output is correct
2 Correct 34 ms 1020 KB Output is correct
3 Runtime error 251 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 1620 KB Output is correct
7 Correct 8 ms 1520 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 8 ms 1620 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 930 ms 100492 KB Output is correct
12 Correct 34 ms 1020 KB Output is correct
13 Runtime error 251 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -