oj.uz

Submission #693225

# Submission time Handle Problem Language Result Execution time Memory
693225 2023-02-02T13:16:02 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;
            if(nex == n + 1)
                break;
            nex = upper_bound(x + 1, x + n + 1, x[nex] + k) - x - 1;
            if(nex == n + 1)
                break;
            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 82 ms 528 KB Output is correct
3 Correct 95 ms 536 KB Output is correct
4 Correct 19 ms 436 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 85 ms 508 KB Output is correct
7 Correct 63 ms 528 KB Output is correct
8 Correct 74 ms 552 KB Output is correct
9 Correct 44 ms 468 KB Output is correct
10 Correct 86 ms 540 KB Output is correct
11 Correct 88 ms 540 KB Output is correct
12 Correct 19 ms 340 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 82 ms 528 KB Output is correct
3 Correct 95 ms 536 KB Output is correct
4 Correct 19 ms 436 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 85 ms 508 KB Output is correct
7 Correct 63 ms 528 KB Output is correct
8 Correct 74 ms 552 KB Output is correct
9 Correct 44 ms 468 KB Output is correct
10 Correct 86 ms 540 KB Output is correct
11 Correct 88 ms 540 KB Output is correct
12 Correct 19 ms 340 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 2 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 82 ms 528 KB Output is correct
3 Correct 95 ms 536 KB Output is correct
4 Correct 19 ms 436 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 85 ms 508 KB Output is correct
7 Correct 63 ms 528 KB Output is correct
8 Correct 74 ms 552 KB Output is correct
9 Correct 44 ms 468 KB Output is correct
10 Correct 86 ms 540 KB Output is correct
11 Correct 88 ms 540 KB Output is correct
12 Correct 19 ms 340 KB Output is correct
13 Correct 89 ms 468 KB Output is correct
14 Correct 70 ms 468 KB Output is correct
15 Correct 106 ms 508 KB Output is correct
16 Correct 33 ms 340 KB Output is correct
17 Correct 76 ms 468 KB Output is correct
18 Correct 94 ms 468 KB Output is correct
19 Correct 78 ms 468 KB Output is correct
20 Correct 65 ms 484 KB Output is correct
21 Execution timed out 2047 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 82 ms 528 KB Output is correct
3 Correct 95 ms 536 KB Output is correct
4 Correct 19 ms 436 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 85 ms 508 KB Output is correct
7 Correct 63 ms 528 KB Output is correct
8 Correct 74 ms 552 KB Output is correct
9 Correct 44 ms 468 KB Output is correct
10 Correct 86 ms 540 KB Output is correct
11 Correct 88 ms 540 KB Output is correct
12 Correct 19 ms 340 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 82 ms 528 KB Output is correct
3 Correct 95 ms 536 KB Output is correct
4 Correct 19 ms 436 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 85 ms 508 KB Output is correct
7 Correct 63 ms 528 KB Output is correct
8 Correct 74 ms 552 KB Output is correct
9 Correct 44 ms 468 KB Output is correct
10 Correct 86 ms 540 KB Output is correct
11 Correct 88 ms 540 KB Output is correct
12 Correct 19 ms 340 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 -