Submission #564697

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
564697	2022-05-19T13:29:37 Z	Cookie	Solar Storm (NOI20_solarstorm)	C++14	17 / 100	2000 ms	48076 KB

SolarStorm

#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;
int d[mxn + 3];
int p[mxn + 3];
int main()
{
    int 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]);
       
    }
    int left[n], right[n];
    int 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	6 ms	724 KB	Output is correct
3	Correct	7 ms	724 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	700 KB	Output is correct
7	Correct	6 ms	824 KB	Output is correct
8	Correct	8 ms	956 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	9 ms	836 KB	Output is correct
11	Correct	7 ms	956 KB	Output is correct
12	Correct	3 ms	508 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	27220 KB	Output is correct
2	Correct	336 ms	21680 KB	Output is correct
3	Correct	389 ms	28276 KB	Output is correct
4	Correct	333 ms	30936 KB	Output is correct
5	Correct	429 ms	36172 KB	Output is correct
6	Correct	524 ms	48076 KB	Output is correct
7	Correct	355 ms	31896 KB	Output is correct

Subtask #3

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	6 ms	724 KB	Output is correct
3	Correct	7 ms	724 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	700 KB	Output is correct
7	Correct	6 ms	824 KB	Output is correct
8	Correct	8 ms	956 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	9 ms	836 KB	Output is correct
11	Correct	7 ms	956 KB	Output is correct
12	Correct	3 ms	508 KB	Output is correct
13	Correct	81 ms	27220 KB	Output is correct
14	Correct	336 ms	21680 KB	Output is correct
15	Correct	389 ms	28276 KB	Output is correct
16	Correct	333 ms	30936 KB	Output is correct
17	Correct	429 ms	36172 KB	Output is correct
18	Correct	524 ms	48076 KB	Output is correct
19	Correct	355 ms	31896 KB	Output is correct
20	Incorrect	47 ms	17432 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2098 ms	31596 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	6 ms	724 KB	Output is correct
3	Correct	7 ms	724 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	700 KB	Output is correct
7	Correct	6 ms	824 KB	Output is correct
8	Correct	8 ms	956 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	9 ms	836 KB	Output is correct
11	Correct	7 ms	956 KB	Output is correct
12	Correct	3 ms	508 KB	Output is correct
13	Incorrect	1 ms	704 KB	Output isn't correct
14	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	6 ms	724 KB	Output is correct
3	Correct	7 ms	724 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	700 KB	Output is correct
7	Correct	6 ms	824 KB	Output is correct
8	Correct	8 ms	956 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	9 ms	836 KB	Output is correct
11	Correct	7 ms	956 KB	Output is correct
12	Correct	3 ms	508 KB	Output is correct
13	Correct	81 ms	27220 KB	Output is correct
14	Correct	336 ms	21680 KB	Output is correct
15	Correct	389 ms	28276 KB	Output is correct
16	Correct	333 ms	30936 KB	Output is correct
17	Correct	429 ms	36172 KB	Output is correct
18	Correct	524 ms	48076 KB	Output is correct
19	Correct	355 ms	31896 KB	Output is correct
20	Incorrect	47 ms	17432 KB	Output isn't correct
21	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	6 ms	724 KB	Output is correct
3	Correct	7 ms	724 KB	Output is correct
4	Correct	4 ms	596 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	700 KB	Output is correct
7	Correct	6 ms	824 KB	Output is correct
8	Correct	8 ms	956 KB	Output is correct
9	Correct	5 ms	596 KB	Output is correct
10	Correct	9 ms	836 KB	Output is correct
11	Correct	7 ms	956 KB	Output is correct
12	Correct	3 ms	508 KB	Output is correct
13	Correct	81 ms	27220 KB	Output is correct
14	Correct	336 ms	21680 KB	Output is correct
15	Correct	389 ms	28276 KB	Output is correct
16	Correct	333 ms	30936 KB	Output is correct
17	Correct	429 ms	36172 KB	Output is correct
18	Correct	524 ms	48076 KB	Output is correct
19	Correct	355 ms	31896 KB	Output is correct
20	Incorrect	47 ms	17432 KB	Output isn't correct
21	Halted	0 ms	0 KB	-