oj.uz

Submission #724623

# Submission time Handle Problem Language Result Execution time Memory
724623 2023-04-15T16:43:34 Z TimDee Homecoming (BOI18_homecoming) C++17
31 / 100
 910 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 ll inf = 1e18;
const int mod = 998244353;

int sz=1<<22;
const int _sz=1<<22;
ll t[2*_sz];
ll lazy[2*_sz];
void push(int v) {
    t[v]+=lazy[v];
    if (2*v+1<2*sz) lazy[2*v+1]+=lazy[v];
    if (2*v+2<2*sz) lazy[2*v+2]+=lazy[v];
    lazy[v]=0;
}
ll 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;
    ll lq=query(2*v+1,l,m,lx,rx);
    ll rq=query(2*v+2,m,r,lx,rx);
    t[v]=max(t[2*v+1],t[2*v+2]);
    return max(lq,rq);
}
ll query(int l, int r) {
    return query(0,0,sz,l,r);
}
void add(int v, int l, int r, int lx, int rx, ll 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, ll x) {
    add(0,0,sz,l,r,x);
}

long long solve(int N, int K, int *A, int *B) {
    #define int long long

    int n=N, k=K;
    sz=1; while (sz<2*n+1) sz<<=1;
    forn(i,2*sz) t[i]=lazy[i]=0;
    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<ll> 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<ll> dp(2*n+1,0);

    for (int i=1; i<=2*n; ++i) {
        dp[i]=max(dp[i],dp[i-1]);
        ll sub=(i>=n)?dp[i-n]:0;
        int l=max(0ll,i-n);
        int r=i;
        ll x=query(l,r);
        dp[i] = max(dp[i],x+a[i-1]-(prb[i+k-1]-prb[i-1])-sub);
        add(i,i+1,dp[i]);
        add(0,i,a[i-1]-b[i-1]);
        if (i+k-1>=n) 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 | //   \ __ __  \
      | ^

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 8 ms 1364 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 7 ms 1392 KB Output is correct
10 Correct 4 ms 340 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 84088 KB Output is correct
2 Correct 33 ms 600 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 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 8 ms 1364 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 7 ms 1392 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 910 ms 84088 KB Output is correct
12 Correct 33 ms 600 KB Output is correct
13 Runtime error 251 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -