oj.uz

답안 #693249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
693249 2023-02-02T13:47:56 Z saayan007 Solar Storm (NOI20_solarstorm) C++17
10 / 100
 646 ms 262144 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 sum[n + 1];
    sum[0] = 0;
    fur(i, 1, n) {
        sum[i] = sum[i - 1] + v[i];
    }

    ll res = 0;
    ll dp[n + 1][s + 1] = {};
    ll frst[n + 1][s + 1] = {};
    ll prev[n + 1] = {};
    fur(i, 1, n) {
        frst[i][1] = i;
    }

    fur(j, 2, s) {
        fur(i, 1, n) {
            ll pr = lower_bound(x + 1, x + n + 1, x[i] - k) - x - 1;
            pr = lower_bound(x + 1, x + n + 1, x[pr] - k) - x;
            frst[i][j] = frst[pr][j - 1];
            prev[i] = pr;
        }
    }

    ll right = 0, num = 0;
    fur(i, 1, n) {
        fur(j, 1, s) {
            ll l = frst[i][j];

            ll lt = lower_bound(x + 1, x + n + 1, x[l] - k) - x - 1;
            ll rt = upper_bound(x + 1, x + n + 1, x[i] + k) - x - 1;

            dp[i][j] = sum[rt] - sum[lt];
            if(dp[i][j] > res) {
                res = dp[i][j];
                right = i; num = j;
            }
        }
    }

    vl ans;
    while(num--) {
        ans.eb(right);
        right = prev[right];
    }
    reverse(all(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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 646 ms 159788 KB Output is correct
14 Correct 49 ms 5972 KB Output is correct
15 Correct 139 ms 12992 KB Output is correct
16 Correct 22 ms 2772 KB Output is correct
17 Correct 44 ms 5332 KB Output is correct
18 Correct 25 ms 2948 KB Output is correct
19 Correct 44 ms 5204 KB Output is correct
20 Correct 81 ms 9340 KB Output is correct
21 Runtime error 98 ms 262144 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 944 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 3 ms 980 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -