oj.uz

Submission #724659

# Submission time Handle Problem Language Result Execution time Memory
724659 2023-04-15T17:20:01 Z TimDee Homecoming (BOI18_homecoming) C++17
31 / 100
 780 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);
    }
    int lx,rx,x;
    void addd(int v, int l, int r) {
        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;
        addd(2*v+1,l,m);
        addd(2*v+2,m,r);
        t[v]=max(t[2*v+1],t[2*v+2]);
    }
    void add(int l, int r, int _x) {
        lx=l,rx=r,x=_x;
        addd(0,0,sz);
    }
};

#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 (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:81:15: warning: unused variable 'inf' [-Wunused-variable]
   81 |     const int inf = 1e18;
      |               ^~~
homecoming.cpp:83:9: warning: unused variable 'ans' [-Wunused-variable]
   83 |     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 1 ms 340 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 1 ms 340 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 7 ms 672 KB Output is correct
9 Correct 6 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 780 ms 84712 KB Output is correct
2 Correct 30 ms 1004 KB Output is correct
3 Runtime error 267 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 1 ms 340 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 7 ms 672 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 780 ms 84712 KB Output is correct
12 Correct 30 ms 1004 KB Output is correct
13 Runtime error 267 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -