제출 #1136807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136807		Roumak77	Solar Storm (NOI20_solarstorm)	C++20	62 / 100	2093 ms	37288 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

    6) S ≤ 50 -> 16 points
    7) No constraints -> 30 points


    Total = 54

 */


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];
    vector<ll> fin(s);
    for(ll i = 0; i < s; i++){
        fin[i] = i;
    }
    ll Ubound = n;
    for(ll i = 0; i < n; i++){
        if(i >= Ubound){
            break;
        }
        ll rem = s;
        vector<ll> temp;
        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;
            }
        }

        rem--;
        temp.push_back(i);


        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 start = r1;
        ll end = l2;

        while(rem > 0){
            ll new_idx = end + 1;
            if(new_idx >= n){
                break;
            }
            ll l = new_idx;
            ll r = n;
            while(l + 1 < r){
                ll mid = (l + r)/2;
                if(list_n[mid] - list_n[new_idx] <= k){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            rem--;
            ll new_add = l;
            temp.push_back(l);
            r = n;
            while(l + 1 < r){
                ll mid = (l + r)/2;
                if(list_n[mid] - list_n[new_add] <= k){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            end =  l;
        }
        if(r1 > 0 && Ubound == n && fin.size() >= 2 && (rem > 0 || end == n - 1)){
            Ubound = fin[1];
        }
        ll val = pref[end + 1] - pref[start];
        if(val > curr_max){
            fin = temp;
            curr_max = val;
        }


    }

    cout << fin.size() << endl;
    for(ll i : fin){
        cout << i + 1 << " ";

    }

    //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: 18 / 18
• Subtask 6: 16 / 16
• Subtask 7: 0 / 30