oj.uz

Submission #724624

# Submission time Handle Problem Language Result Execution time Memory
724624 2023-04-15T16:45:44 Z TimDee Homecoming (BOI18_homecoming) C++17
31 / 100
 918 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);
}
const int N=2e6;
ll pra[2*N+1];
ll prb[3*N+1];
int a[2*N];
int b[2*N];

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;
    forn(i,2*n) a[i]=A[i%n], b[i]=B[i%n];
    forn(i,2*n) pra[i+1]=pra[i]+A[i%n];
    forn(i,3*n) prb[i+1]=prb[i]+B[i%n];
    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 0 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 0 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 1236 KB Output is correct
7 Correct 8 ms 1280 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 7 ms 1236 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 918 ms 72340 KB Output is correct
2 Correct 33 ms 468 KB Output is correct
3 Runtime error 255 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 0 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 1236 KB Output is correct
7 Correct 8 ms 1280 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 7 ms 1236 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 918 ms 72340 KB Output is correct
12 Correct 33 ms 468 KB Output is correct
13 Runtime error 255 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -