oj.uz

Submission #693226

# Submission time Handle Problem Language Result Execution time Memory
693226 2023-02-02T13:16:44 Z saayan007 Solar Storm (NOI20_solarstorm) C++17
10 / 100
 2000 ms 852 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define fur(i, a, b) for(ll i = a; i <= (ll) b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll) b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define nl "\n"

const ll mxn = 1e4L + 1;
#warning mxn is according to subtask
ll n, s, k;
ll d[mxn];
ll v[mxn];
ll x[mxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> s >> k;

    fur(i, 1, n - 1) {
        cin >> d[i];
    }

    fur(i, 1, n) {
        cin >> v[i];
    }

    x[1] = 0;
    fur(i, 2, n) {
        x[i] = x[i - 1] + d[i - 1];
    }

    ll res = 0;
    vl ans;
    vl tmp;
    fur(i, 1, n) {
        tmp.clear();
        ll lt = i;
        ll cur = i;
        tmp.pb(cur);
        fur(j, 2, s) {
            ll nex = upper_bound(x + 1, x + n + 1, x[cur] + k) - x;
            nex = upper_bound(x + 1, x + n + 1, x[nex] + k) - x - 1;
            cur = nex;
            tmp.pb(nex);
        }
        ll rt = cur;

        ll opt = 0;
        fur(j, 1, n) {
            if(j < lt) {
                if(x[j] + k >= x[lt])
                    opt += v[j];
            } else if(j > rt) {
                if(x[rt] + k >= x[j])
                    opt += v[j];
            } else {
                opt += v[j];
            }
        }

        if(res < opt) {
            res = opt;
            swap(tmp, ans);
        }
    }

    cout << ans.size() << nl;
    for(auto u : ans)
        cout << u << ' ';
    cout << nl;
}

Compilation message

SolarStorm.cpp:24:2: warning: #warning mxn is according to subtask [-Wcpp]
   24 | #warning mxn is according to subtask
      |  ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 101 ms 524 KB Output is correct
3 Correct 133 ms 540 KB Output is correct
4 Correct 25 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 69 ms 468 KB Output is correct
7 Correct 82 ms 520 KB Output is correct
8 Correct 105 ms 536 KB Output is correct
9 Correct 49 ms 472 KB Output is correct
10 Correct 112 ms 544 KB Output is correct
11 Correct 118 ms 540 KB Output is correct
12 Correct 20 ms 436 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 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 101 ms 524 KB Output is correct
3 Correct 133 ms 540 KB Output is correct
4 Correct 25 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 69 ms 468 KB Output is correct
7 Correct 82 ms 520 KB Output is correct
8 Correct 105 ms 536 KB Output is correct
9 Correct 49 ms 472 KB Output is correct
10 Correct 112 ms 544 KB Output is correct
11 Correct 118 ms 540 KB Output is correct
12 Correct 20 ms 436 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 101 ms 524 KB Output is correct
3 Correct 133 ms 540 KB Output is correct
4 Correct 25 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 69 ms 468 KB Output is correct
7 Correct 82 ms 520 KB Output is correct
8 Correct 105 ms 536 KB Output is correct
9 Correct 49 ms 472 KB Output is correct
10 Correct 112 ms 544 KB Output is correct
11 Correct 118 ms 540 KB Output is correct
12 Correct 20 ms 436 KB Output is correct
13 Correct 398 ms 568 KB Output is correct
14 Correct 100 ms 508 KB Output is correct
15 Correct 129 ms 508 KB Output is correct
16 Correct 42 ms 440 KB Output is correct
17 Correct 84 ms 492 KB Output is correct
18 Correct 119 ms 540 KB Output is correct
19 Correct 94 ms 504 KB Output is correct
20 Correct 80 ms 484 KB Output is correct
21 Execution timed out 2070 ms 852 KB Time limit exceeded
22 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 101 ms 524 KB Output is correct
3 Correct 133 ms 540 KB Output is correct
4 Correct 25 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 69 ms 468 KB Output is correct
7 Correct 82 ms 520 KB Output is correct
8 Correct 105 ms 536 KB Output is correct
9 Correct 49 ms 472 KB Output is correct
10 Correct 112 ms 544 KB Output is correct
11 Correct 118 ms 540 KB Output is correct
12 Correct 20 ms 436 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 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 101 ms 524 KB Output is correct
3 Correct 133 ms 540 KB Output is correct
4 Correct 25 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 69 ms 468 KB Output is correct
7 Correct 82 ms 520 KB Output is correct
8 Correct 105 ms 536 KB Output is correct
9 Correct 49 ms 472 KB Output is correct
10 Correct 112 ms 544 KB Output is correct
11 Correct 118 ms 540 KB Output is correct
12 Correct 20 ms 436 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -