oj.uz

Submission #693616

# Submission time Handle Problem Language Result Execution time Memory
693616 2023-02-03T05:56:26 Z zeroesandones Solar Storm (NOI20_solarstorm) C++17
10 / 100
 207 ms 42288 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back

void solve()
{
    // done : 1, 2, 4
    // trial at subtask 3
    // idea for subtask 5:
    // for every range, check if this range can be covered
    // might be binary search check if this value can be achieved
    ll n, s, k;
    cin >> n >> s >> k;

    ll d[n - 1];
    FOR(i, 0, n - 1)
        cin >> d[i];

    ll a[n];
    FOR(i, 0, n)
        cin >> a[i];

    ll psum[n] = {};
    psum[0] = a[0];
    FOR(i, 1, n)
        psum[i] = psum[i - 1] + a[i];

    ll pos[n] = {};
    pos[0] = 0;
    for(int i = 1; i < n; ++i) {
        pos[i] = pos[i - 1] + d[i - 1];
    }

    vi left(n, 0), right(n, 0);
    for(int i = 0; i < n; ++i) {
        ll req = pos[i] - k;
        auto it = lower_bound(pos, pos + n, req) - pos;
        left[i] = it;
        req = pos[i] + k + 1;
        it = upper_bound(pos, pos + n, req) - pos;
        right[i] = it - 1;
    }

    pi ans = {0, 0};
    for(int i = 0; i < n; ++i) {
        // the only module will be placed here
        ll curr = psum[right[i]] - (left[i] == 0 ? 0 : psum[left[i] - 1]);
        if(curr > ans.fr) {
            ans = {curr, i};
        }
    }

    cout << 1 << nl;
    cout << ans.sc + 1 << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 456 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 42288 KB Output is correct
2 Correct 200 ms 29636 KB Output is correct
3 Incorrect 171 ms 32724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 456 KB Output is correct
13 Correct 167 ms 42288 KB Output is correct
14 Correct 200 ms 29636 KB Output is correct
15 Incorrect 171 ms 32724 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 39484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 456 KB Output is correct
13 Correct 3 ms 852 KB Output is correct
14 Incorrect 6 ms 716 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 456 KB Output is correct
13 Correct 167 ms 42288 KB Output is correct
14 Correct 200 ms 29636 KB Output is correct
15 Incorrect 171 ms 32724 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 5 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 2 ms 456 KB Output is correct
13 Correct 167 ms 42288 KB Output is correct
14 Correct 200 ms 29636 KB Output is correct
15 Incorrect 171 ms 32724 KB Output isn't correct
16 Halted 0 ms 0 KB -