oj.uz

Submission #693619

# Submission time Handle Problem Language Result Execution time Memory
693619 2023-02-03T05:58:56 Z zeroesandones Solar Storm (NOI20_solarstorm) C++17
28 / 100
 251 ms 55140 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;
        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 3 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 780 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 40524 KB Output is correct
2 Correct 118 ms 25852 KB Output is correct
3 Correct 130 ms 27720 KB Output is correct
4 Correct 155 ms 32268 KB Output is correct
5 Correct 198 ms 37460 KB Output is correct
6 Correct 231 ms 48920 KB Output is correct
7 Correct 166 ms 33144 KB Output is correct

Subtask #3
11.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 3 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 780 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 194 ms 40524 KB Output is correct
14 Correct 118 ms 25852 KB Output is correct
15 Correct 130 ms 27720 KB Output is correct
16 Correct 155 ms 32268 KB Output is correct
17 Correct 198 ms 37460 KB Output is correct
18 Correct 231 ms 48920 KB Output is correct
19 Correct 166 ms 33144 KB Output is correct
20 Correct 126 ms 33092 KB Output is correct
21 Correct 181 ms 40620 KB Output is correct
22 Correct 204 ms 48076 KB Output is correct
23 Correct 160 ms 47256 KB Output is correct
24 Correct 165 ms 44848 KB Output is correct
25 Correct 196 ms 44864 KB Output is correct
26 Correct 163 ms 33444 KB Output is correct
27 Correct 182 ms 42928 KB Output is correct
28 Correct 203 ms 42436 KB Output is correct
29 Correct 251 ms 55140 KB Output is correct
30 Correct 220 ms 45048 KB Output is correct
31 Correct 182 ms 39560 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 37764 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 3 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 780 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Incorrect 2 ms 596 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 3 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 780 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 194 ms 40524 KB Output is correct
14 Correct 118 ms 25852 KB Output is correct
15 Correct 130 ms 27720 KB Output is correct
16 Correct 155 ms 32268 KB Output is correct
17 Correct 198 ms 37460 KB Output is correct
18 Correct 231 ms 48920 KB Output is correct
19 Correct 166 ms 33144 KB Output is correct
20 Correct 126 ms 33092 KB Output is correct
21 Correct 181 ms 40620 KB Output is correct
22 Correct 204 ms 48076 KB Output is correct
23 Correct 160 ms 47256 KB Output is correct
24 Correct 165 ms 44848 KB Output is correct
25 Correct 196 ms 44864 KB Output is correct
26 Correct 163 ms 33444 KB Output is correct
27 Correct 182 ms 42928 KB Output is correct
28 Correct 203 ms 42436 KB Output is correct
29 Correct 251 ms 55140 KB Output is correct
30 Correct 220 ms 45048 KB Output is correct
31 Correct 182 ms 39560 KB Output is correct
32 Correct 209 ms 52944 KB Output is correct
33 Incorrect 171 ms 40600 KB Output isn't correct
34 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 3 ms 724 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 780 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 194 ms 40524 KB Output is correct
14 Correct 118 ms 25852 KB Output is correct
15 Correct 130 ms 27720 KB Output is correct
16 Correct 155 ms 32268 KB Output is correct
17 Correct 198 ms 37460 KB Output is correct
18 Correct 231 ms 48920 KB Output is correct
19 Correct 166 ms 33144 KB Output is correct
20 Correct 126 ms 33092 KB Output is correct
21 Correct 181 ms 40620 KB Output is correct
22 Correct 204 ms 48076 KB Output is correct
23 Correct 160 ms 47256 KB Output is correct
24 Correct 165 ms 44848 KB Output is correct
25 Correct 196 ms 44864 KB Output is correct
26 Correct 163 ms 33444 KB Output is correct
27 Correct 182 ms 42928 KB Output is correct
28 Correct 203 ms 42436 KB Output is correct
29 Correct 251 ms 55140 KB Output is correct
30 Correct 220 ms 45048 KB Output is correct
31 Correct 182 ms 39560 KB Output is correct
32 Incorrect 178 ms 37764 KB Output isn't correct
33 Halted 0 ms 0 KB -