oj.uz

Submission #724627

# Submission time Handle Problem Language Result Execution time Memory
724627 2023-04-15T16:48:23 Z TimDee Homecoming (BOI18_homecoming) C++17
31 / 100
 908 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];
ll dp[2*N+1];
ll sub,x;
int l,r;

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];
    forn(i,2*n+1) dp[i]=0;

    for (int i=1; i<=2*n; ++i) {
        dp[i]=max(dp[i],dp[i-1]);
        sub=(i>=n)?dp[i-n]:0;
        l=max(0,i-n);
        r=i;
        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 9 ms 1320 KB Output is correct
8 Correct 9 ms 596 KB Output is correct
9 Correct 7 ms 1288 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 908 ms 72396 KB Output is correct
2 Correct 32 ms 536 KB Output is correct
3 Runtime error 252 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 9 ms 1320 KB Output is correct
8 Correct 9 ms 596 KB Output is correct
9 Correct 7 ms 1288 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 908 ms 72396 KB Output is correct
12 Correct 32 ms 536 KB Output is correct
13 Runtime error 252 ms 262144 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -