Submission #1136801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136801		Roumak77	Solar Storm (NOI20_solarstorm)	C++20	28 / 100	152 ms	23852 KiB

SolarStorm

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;


/*
 * Subtask Marks Additional Constraints
    1) S = 1, N ≤ 10^4, K ≤ 10^9, di ≤ 10^5 for all 1 ≤ i ≤ N − 1, vi ≤ 10^5, for all 1 ≤ i ≤ N -> 10 points
    2) S = 1, di = 1 for all 1 ≤ i ≤ N − 1 -> 7 points
    3) S = 1 -> 11 points
    5) N ≤ 104 -> 18 points
    6) S ≤ 50 -> 16 points
    7) No constraints -> 30 points


    Total = 8

 */


using ll = long long;

void solve(){


    ll n, s, k;
    cin >> n >> s >> k;
    vector<ll> list_n(n, 0);

    for(ll i = 1; i < n; i++){
        cin >> list_n[i];
        list_n[i] += list_n[i - 1];
    }

    vector<ll> list_k(n);
    vector<ll> pref(n + 1, 0);
    for(ll i = 0; i < n; i++){
        cin >> list_k[i];
        pref[i + 1] = pref[i] + list_k[i];
    }

    ll curr_max = pref[s];
    ll max_idx = 0;

    for(ll i = 0; i < n; i++){


        ll l1 = -1;
        ll r1 = i;

        while(l1 + 1 < r1){
            ll mid = (l1 + r1)/2;

            if(list_n[i] - list_n[mid] <= k){
                r1 = mid;
            }else{
                l1 = mid;
            }
        }

        ll l2 = i;
        ll r2 = n;
        while(l2 + 1 < r2){
            ll mid = (l2 + r2)/2;
            if(list_n[mid] - list_n[i] <= k){
                l2 = mid;
            }else{
                r2 = mid;
            }
        }
        ll val = pref[l2 + 1] - pref[r1];
        if(val > curr_max){
            curr_max = val;
            max_idx = i;
        }

    }

    cout << s << endl;
    for(ll i = 0; i < s; i++){
        max_idx++;
        cout << min(n, max_idx) << " ";

    }

    //cout << curr_max << endl;





}

bool single = true;

signed main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if(!single) cin >> t;

    while(t--){
        solve();
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 0 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30