oj.uz

답안 #784325

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
784325 2023-07-16T02:57:52 Z Cookie Solar Storm (NOI20_solarstorm) C++14
28 / 100
 99 ms 30952 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e16;
const int mxn = 1e5 + 5;
 
int n, s; ll k;
int up[mxn + 1][20], tor[mxn + 1];
ll d[mxn + 1], pd[mxn + 1], pv[mxn + 1], v[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> k;
    for(int i = 2; i <= n; i++){
        cin >> d[i]; pd[i] = pd[i - 1] + d[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> v[i]; pv[i] = pv[i - 1] + v[i];
    }
    int r = 1;
    for(int i = 1; i <= n; i++){
        r = max(r, i);
        while(r <= n && pd[r] - pd[i] <= k)r++;
        tor[i] = r - 1; 
        //cout << tor[i] << " ";
    }
    for(int i = 1; i <= n; i++){
        up[i][0] = tor[tor[i]];
    }
    
    for(int i = 1; i < 19; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[min(up[j][i - 1] + 1, n)][i - 1];
        }
    }
    
    ll ans = 0, idl = 0;
    for(int i = 1; i <= n; i++){
        int r = i;
        for(int j = 0; j < 20; j++){
            if(s & (1 << j)){
                r = up[r][j] + 1;
                if(r == n + 1)break;
            }
        }
        r--;
        if(pv[r] - pv[i - 1] > ans){
            ans = pv[r] - pv[i - 1];
            idl = i;
        }
    }
    vt<int>res;
    while(idl <= n && s--){
        res.pb(tor[idl]); idl = up[idl][0] + 1;
    }
    cout << sz(res) << "\n";
    for(auto i: res){
        cout << i << " ";
    }
    return(0);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 1376 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1500 KB Output is correct
9 Correct 2 ms 1092 KB Output is correct
10 Correct 3 ms 1512 KB Output is correct
11 Correct 3 ms 1548 KB Output is correct
12 Correct 2 ms 860 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 99 ms 30952 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 1376 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1500 KB Output is correct
9 Correct 2 ms 1092 KB Output is correct
10 Correct 3 ms 1512 KB Output is correct
11 Correct 3 ms 1548 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Runtime error 99 ms 30952 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 93 ms 30352 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 1376 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1500 KB Output is correct
9 Correct 2 ms 1092 KB Output is correct
10 Correct 3 ms 1512 KB Output is correct
11 Correct 3 ms 1548 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 3 ms 1620 KB Output is correct
14 Correct 3 ms 1380 KB Output is correct
15 Correct 2 ms 1252 KB Output is correct
16 Correct 2 ms 988 KB Output is correct
17 Correct 3 ms 1256 KB Output is correct
18 Correct 3 ms 1564 KB Output is correct
19 Correct 2 ms 1364 KB Output is correct
20 Correct 2 ms 1108 KB Output is correct
21 Correct 4 ms 1748 KB Output is correct
22 Correct 3 ms 1620 KB Output is correct
23 Correct 3 ms 1492 KB Output is correct
24 Correct 2 ms 1364 KB Output is correct
25 Correct 3 ms 1500 KB Output is correct
26 Correct 3 ms 1504 KB Output is correct
27 Correct 2 ms 1236 KB Output is correct
28 Correct 2 ms 1240 KB Output is correct
29 Correct 2 ms 1236 KB Output is correct
30 Correct 6 ms 1492 KB Output is correct

Subtask #6
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 1376 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1500 KB Output is correct
9 Correct 2 ms 1092 KB Output is correct
10 Correct 3 ms 1512 KB Output is correct
11 Correct 3 ms 1548 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Runtime error 99 ms 30952 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 1376 KB Output is correct
3 Correct 3 ms 1492 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1500 KB Output is correct
9 Correct 2 ms 1092 KB Output is correct
10 Correct 3 ms 1512 KB Output is correct
11 Correct 3 ms 1548 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Runtime error 99 ms 30952 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -