Submission #209762

#	Time	Username	Problem	Language	Result	Execution time	Memory
209762		Alexa2001	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	221 ms	113248 KiB

SolarStorm

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int Nmax = 1e6 + 5, lg = 20;

// 15 : 38

int go[lg+1][Nmax], n, S, deploy[Nmax];
ll coef[Nmax], d[Nmax], K;


const int bsize = 1 << 18;
char buffer[bsize+2]; int cursor;


static inline void init_read()
{
    fread(buffer, 1, bsize, stdin), cursor = 0;
}

template<typename T>
void read(T &x)
{
    x = 0;
    while(!isdigit(buffer[cursor]))
    {
        ++cursor;
        if(cursor == bsize) init_read();
    }
    while(isdigit(buffer[cursor]))
    {
        x = x * 10 + buffer[cursor] - '0';
        ++cursor;
        if(cursor == bsize) init_read();
    }
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    init_read();
    read(n); read(S); read(K);

    int i;
    for(i=2; i<=n; ++i)
    {
        read(d[i]);
        d[i] += d[i-1];
    }

    for(i=1; i<=n; ++i) read(coef[i]), coef[i] += coef[i-1];

    d[n+1] = 1e18;

    int j, k;
    j = 1; k = 2;

    for(i=1; i<=n; ++i)
    {
        while(d[j+1] - d[i] <= K) ++j;
        while(d[k] - d[j] <= K) ++k;

        go[0][i] = k;
        deploy[i] = j;
    }

    go[0][n+1] = n+1;

    for(j=1; j<=lg; ++j)
        for(i=1; i<=n+1; ++i)
            go[j][i] = go[j-1][go[j-1][i]];

    ll ans = -1;
    int start, finish;

    for(i=1; i<=n; ++i)
    {
        int to = i;

        for(j=0; j<=lg; ++j)
            if(S & (1<<j))
                to = go[j][to];

        ll curr = coef[to-1] - coef[i-1];

        if(curr > ans)
            ans = curr, start = i, finish = to - 1;
    }

    vector<int> Ans;

    while(start <= finish)
    {
        Ans.push_back(deploy[start]);
        start = go[0][start];
    }

    cout << Ans.size() << '\n';
    for(auto it : Ans) cout << it << ' ';

    return 0;
}

Compilation message (stderr)

SolarStorm.cpp: In function 'void init_read()':
SolarStorm.cpp:20:35: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread(buffer, 1, bsize, stdin), cursor = 0;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:96:17: warning: 'finish' may be used uninitialized in this function [-Wmaybe-uninitialized]
     while(start <= finish)
           ~~~~~~^~~~~~~~~
SolarStorm.cpp:99:15: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
         start = go[0][start];
         ~~~~~~^~~~~~~~~~~~~~

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