oj.uz

Submission #564691

# Submission time Handle Problem Language Result Execution time Memory
564691 2022-05-19T13:21:07 Z Cookie Solar Storm (NOI20_solarstorm) C++14
0 / 100
 2000 ms 38528 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;
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; 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 5 ms 832 KB Output is correct
3 Incorrect 6 ms 852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 27328 KB Output is correct
2 Incorrect 278 ms 26576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 5 ms 832 KB Output is correct
3 Incorrect 6 ms 852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 38528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 5 ms 832 KB Output is correct
3 Incorrect 6 ms 852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 5 ms 832 KB Output is correct
3 Incorrect 6 ms 852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 5 ms 832 KB Output is correct
3 Incorrect 6 ms 852 KB Output isn't correct
4 Halted 0 ms 0 KB -