oj.uz

Submission #564699

# Submission time Handle Problem Language Result Execution time Memory
564699 2022-05-19T13:30:57 Z Cookie Solar Storm (NOI20_solarstorm) C++14
28 / 100
 2000 ms 66792 KB 
#include <bits/stdc++.h>
using namespace std;
#define LIFESUCKS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ld long double
#define ar array
#include<cstdio>
#define vt vector
#include<fstream>
//ifstream fin("QUANMA.INP");
//ofstream fout("QUANMA.OUT");
#include<fstream>
#define pb push_back
#define all(c) (c).begin(), (c).end()
//#define length(x) (int)(x).size()
#define fi first
#define se second
#define vt vector
const int mxn = 1e6;
ll d[mxn + 3];
ll p[mxn + 3];
int main()
{
    ll n, s, k; cin >> n >> s >> k;
    ll crpos = 0;
    vt<ll>prefd; prefd.pb(0);
    vt<ll>prefp; prefp.pb(0);
    
    for(int i = 0; i < n - 1; i++){
        cin >> d[i];
        prefd.pb(prefd[i] + d[i]);
        
    }
    for(int i = 0; i < n; i++){
        cin >> p[i];
        prefp.pb(prefp[i] + p[i]);
       
    }
    ll left[n], right[n];
    ll id[n];
    left[0] = 0;
    for(int i = 1; i < n; i++){
        int l = 0, r = i - 1, ans = i;
        while(l <= r){
            //cout << "aa";
            int mid = (l + r) / 2;
            if(prefd[i] - prefd[mid] <= k){
                ans = mid; r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        left[i] = ans;
    }
    right[n - 1] = n - 1;
    for(int i = n - 2; i >= 0; i--){
        int l = i + 1, r = n - 1, ans = i;
        while(l <= r){
            int mid = (l + r) / 2;
            if(prefd[mid] - prefd[i] <= k){
                
                ans = mid; l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        right[i] = ans;
    }
    
    int cr = n - 1;
    int mx[n];
    for(int i = n - 1; i >= 0; i--){
        while(cr >= left[i]){
            mx[cr] = right[i];
            id[cr] = i; 
            cr--;
        }
    }
    
    ll ans = 0, idd = -1;
    for(int i = 0; i < n; i++){
        ll curr = p[i], pos = i;
        for(int j = 0; j < s; j++){
            
            if(pos == n - 1)break;
            
            curr += prefp[mx[pos] + 1] - prefp[pos + 1];
            pos = mx[pos];
            
        }
        if(curr > ans){
            idd = i; 
            ans = curr;
        }
    }
    
    vt<int>anss; anss.pb(id[idd]);
    int pos = idd;
    for(int i = 0; i < s - 1; i++){
        if(pos == n - 1)break;
        pos = mx[pos] + 1;
        if(pos == n)break;
        anss.pb(id[pos]);
        
    }
    
    cout << anss.size() << "\n";
    for(auto i: anss)cout << i + 1 << " ";
    return 0;
}

Compilation message

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:25:8: warning: unused variable 'crpos' [-Wunused-variable]
   25 |     ll crpos = 0;
      |        ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 5 ms 908 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 6 ms 1008 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 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 412 ms 50748 KB Output is correct
2 Correct 280 ms 32340 KB Output is correct
3 Correct 312 ms 34860 KB Output is correct
4 Correct 302 ms 37796 KB Output is correct
5 Correct 357 ms 44292 KB Output is correct
6 Correct 495 ms 58904 KB Output is correct
7 Correct 323 ms 38960 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 5 ms 908 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 6 ms 1008 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 412 ms 50748 KB Output is correct
14 Correct 280 ms 32340 KB Output is correct
15 Correct 312 ms 34860 KB Output is correct
16 Correct 302 ms 37796 KB Output is correct
17 Correct 357 ms 44292 KB Output is correct
18 Correct 495 ms 58904 KB Output is correct
19 Correct 323 ms 38960 KB Output is correct
20 Correct 362 ms 32368 KB Output is correct
21 Correct 420 ms 48732 KB Output is correct
22 Correct 487 ms 57624 KB Output is correct
23 Correct 460 ms 56952 KB Output is correct
24 Correct 467 ms 53604 KB Output is correct
25 Correct 489 ms 53680 KB Output is correct
26 Correct 376 ms 40168 KB Output is correct
27 Correct 470 ms 51352 KB Output is correct
28 Correct 453 ms 50716 KB Output is correct
29 Correct 599 ms 66084 KB Output is correct
30 Correct 489 ms 54080 KB Output is correct
31 Correct 413 ms 47376 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 47256 KB Time limit exceeded
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 5 ms 908 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 6 ms 1008 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 7 ms 980 KB Output is correct
14 Correct 7 ms 852 KB Output is correct
15 Incorrect 8 ms 852 KB Output isn't correct
16 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 5 ms 908 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 6 ms 1008 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 412 ms 50748 KB Output is correct
14 Correct 280 ms 32340 KB Output is correct
15 Correct 312 ms 34860 KB Output is correct
16 Correct 302 ms 37796 KB Output is correct
17 Correct 357 ms 44292 KB Output is correct
18 Correct 495 ms 58904 KB Output is correct
19 Correct 323 ms 38960 KB Output is correct
20 Correct 362 ms 32368 KB Output is correct
21 Correct 420 ms 48732 KB Output is correct
22 Correct 487 ms 57624 KB Output is correct
23 Correct 460 ms 56952 KB Output is correct
24 Correct 467 ms 53604 KB Output is correct
25 Correct 489 ms 53680 KB Output is correct
26 Correct 376 ms 40168 KB Output is correct
27 Correct 470 ms 51352 KB Output is correct
28 Correct 453 ms 50716 KB Output is correct
29 Correct 599 ms 66084 KB Output is correct
30 Correct 489 ms 54080 KB Output is correct
31 Correct 413 ms 47376 KB Output is correct
32 Correct 595 ms 63256 KB Output is correct
33 Correct 442 ms 48540 KB Output is correct
34 Incorrect 701 ms 66792 KB Output isn't correct
35 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 5 ms 908 KB Output is correct
3 Correct 6 ms 980 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 5 ms 856 KB Output is correct
8 Correct 6 ms 1008 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 412 ms 50748 KB Output is correct
14 Correct 280 ms 32340 KB Output is correct
15 Correct 312 ms 34860 KB Output is correct
16 Correct 302 ms 37796 KB Output is correct
17 Correct 357 ms 44292 KB Output is correct
18 Correct 495 ms 58904 KB Output is correct
19 Correct 323 ms 38960 KB Output is correct
20 Correct 362 ms 32368 KB Output is correct
21 Correct 420 ms 48732 KB Output is correct
22 Correct 487 ms 57624 KB Output is correct
23 Correct 460 ms 56952 KB Output is correct
24 Correct 467 ms 53604 KB Output is correct
25 Correct 489 ms 53680 KB Output is correct
26 Correct 376 ms 40168 KB Output is correct
27 Correct 470 ms 51352 KB Output is correct
28 Correct 453 ms 50716 KB Output is correct
29 Correct 599 ms 66084 KB Output is correct
30 Correct 489 ms 54080 KB Output is correct
31 Correct 413 ms 47376 KB Output is correct
32 Execution timed out 2080 ms 47256 KB Time limit exceeded
33 Halted 0 ms 0 KB -