Submission #1078208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078208		whyalwaysmezzz	Solar Storm (NOI20_solarstorm)	C++17	0 / 100	134 ms	70740 KiB

SolarStorm

// Author: ChungNotTrung;
// Created: 2024-08-26 12:18:53
// Problem: None
// Tag: None
// Source: None
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db long double
#define int long long

#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define All(x) x.begin(), x.end()

#define file(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".out", "w", stdout) : 0
#define file_trau(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".ans", "w", stdout) : 0
#define Faster ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define Run_time cerr << " Time : " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n"

#define bit(i, n) (1ll && ((1ll << i) & (n)))
#define ONBIT(i, mask) ((1ll << i) | (mask))
#define OFFBIT(i, mask) ((~(1ll << i)) & (mask))
#define MASK(n) (1ll << (n))
#define cnt_bit(n) (__builtin_popcountll(n))
#define Lg2(n) (63 - __builtin_clzll(n))

#define rep(i, x, n) for (int i = x; i <= n; ++i)
#define repd(i, n, x) for (int i = n; i >= x; --i)
#define repv(i, n) for (auto &i : n)

#define as_vi(v, n, val) v.assign(n + 1, val)
#define as_vvi(v, n, m, val) v.assign(n + 1, vi(m + 1, val))
#define as_vvvi(v, n, m, k, val) v.assign(n + 1, vvi(m + 1, vi(k + 1, val)))

#define left(id) (id << 1ll)
#define right(id) (id << 1ll | 1)

mt19937 rd(chrono::steady_clock().now().time_since_epoch().count());
int rng(int l, int r) { return uniform_int_distribution<int>(l, r)(rd); }
vi dx{0, 0, 1, -1, 1, 1, -1, -1};
vi dy{1, -1, 0, 0, -1, 1, -1, 1};

template <class X, class Y>
bool maximize(X &a, const Y &b)
{
    if (a < b)
        return a = b, true;
    return false;
}

template <class X, class Y>
bool minimize(X &a, const Y &b)
{
    if (a > b)
        return a = b, true;
    return false;
}
const int base = 311;
const int nmax = 1e6 + 10;
const int oo = 1e18 + 100;
const int MOD = 1e9 + 7;
int sqr(int x)
{
    return x * x;
}

int POW(int a, int n)
{
    int res = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        n /= 2;
    }
    return res;
}

void fixmod(int &val)
{
    if (val < 0)
        val = (val + MOD * MOD) % MOD;
    if (val >= MOD)
        val %= MOD;
}

int ntest;
int n,k,r;
int a[nmax],d[nmax],pos[nmax];
namespace sub1{
    int pf[nmax];
    int sum(int l,int r){
        return pf[r]-pf[l-1];
    }
    void solve(){
        rep(i,1,n){
            pf[i]=pf[i-1]+a[i];
        }
        int left=1,right=1;
        int ans=0;
        rep(i,1,n){
            while(pos[i]-pos[left]>r) left++;
            while(pos[right]-pos[i]<=r&&right<n) right++;
            if(pos[right]-pos[i]>r) right--;
            maximize(ans,sum(left,right));
        }
        cout << ans;
    }
}
namespace trau{
    int p[nmax],pf[nmax];
    ii f[nmax];
    int sum(int l,int r){
        return pf[r]-pf[l-1];
    }
    int next(int id){
        if(id>n) return n;
        int l=id,h=n;
        while(l<=h){
            int mid=l+h>>1;
            if(pos[mid]-pos[id]>r){
                h=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return h;
    }
    // fi kq
    // se cnt
    int dp(int id,int cnt){
        if(cnt==0||id>=n) return id;
        int res=0;
        if(f[id].fi!=0){
            if(cnt==f[id].se){
                res=f[id].fi;
            }
            else
            {
                res=dp(p[p[f[id].fi+1]],cnt-f[id].se-1);
            }
        }
        else
        {
            res=dp(p[p[id+1]],cnt-1);
        }
        f[id]={res,cnt};
        return res;
    }
    void solve(){
        pos[n+1]=oo;
        rep(i,1,n+3){
            p[i]=next(i);
            pf[i]=pf[i-1]+a[i];
        }
        int ans=0;
        rep(i,1,n){
            int j=dp(p[p[i]],k-1);
            maximize(ans,sum(i,j));
//            cout << i << ' ' << j << ' ' << sum(i,j) << '\n';
        }
        cout << ans;
    }
}
void TryHard()
{
    cin >> n >> k >> r;
    rep(i,1,n-1){
        cin >> d[i];
    }
    pos[1]=0;
    rep(i,2,n){
        pos[i]=pos[i-1]+d[i-1];
    }
//    rep(i,1,n){
//        cout << pos[i] << ' ';
//    }
//    cout << "\n\n";
    rep(i,1,n){
        cin >> a[i];
    }
//    cout << '\n';
    // if(k==1)
    // sub1::solve();
    // else
    trau::solve();

}
main()
{

    // Learning is like rowing upstream, not to advance is to drop back .
    // A winner never stops trying .
    Faster;
    file("SPACE");
    // file_trau("");
    ntest = 1;
    while (ntest--)
    {
        TryHard();
        cout << "\n";
    }
}

// LIMIT :

Compilation message (stderr)

SolarStorm.cpp: In function 'long long int trau::next(long long int)':
SolarStorm.cpp:129:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  129 |             int mid=l+h>>1;
      |                     ~^~
SolarStorm.cpp: At global scope:
SolarStorm.cpp:200:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  200 | main()
      | ^~~~
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:23:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 | #define file(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".out", "w", stdout) : 0
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
SolarStorm.cpp:206:5: note: in expansion of macro 'file'
  206 |     file("SPACE");
      |     ^~~~
SolarStorm.cpp:23:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 | #define file(name) fopen(name ".inp", "r") ? freopen(name ".inp", "r", stdin), freopen(name ".out", "w", stdout) : 0
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
SolarStorm.cpp:206:5: note: in expansion of macro 'file'
  206 |     file("SPACE");
      |     ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30