제출 #1119867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119867		peacebringer1667	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	400 ms	130520 KiB

SolarStorm

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define db double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int alp = 20;
const int maxn = 1e6 + 5;

template <typename t> inline void mini(t &x,t y){if (x > y) x = y;}
template <typename t> inline void maxi(t &x,t y){if (x < y) x = y;}
template <typename t> inline bool maximized(t &x,t y){if (x < y){x = y; return 1;}return 0;}


int spt[maxn][alp + 2],nxt[maxn];
ll dist[maxn],V[maxn];

void input(int n,int s,ll k){
	for (int i = 2 ; i <= n ; i++)
		cin >> dist[i];
		
	for (int i = 1 ; i <= n ; i++) cin >> V[i];
}

void prepare(int n,ll k){
	//prepare distance and sum of value->V 
	for (int i = 2 ; i <= n ; i++){
		dist[i] += dist[i - 1];
		V[i] += V[i - 1];
	}
    
    //prepare maximum point from i,dist(i->p) <= k
    int p = n;
    for (int i = n ; i > 0 ; i--){
    	while (p > i && dist[p] - dist[i] > k) p--;
    	nxt[i] = p;
	}
	
	//preparing sparse table
	//initialize to n + 1
	for (int i = 1 ; i <= n + 1 ; i++)
	  for (int j = 0 ; j <= alp ; j++)
	    spt[i][j] = n + 1;
	
	//next point p : a machine is placed->(i->p - 1) 
	for (int i = n ; i > 0 ; i--){
		int p = nxt[nxt[i]] + 1;
		spt[i][0] = p;
		for (int j = 1 ; j <= alp ; j++)
		  spt[i][j] = spt[spt[i][j - 1]][j - 1];
	}
}


ll profit(int x,int n,int s){
	int y = x;
	
	for (int i = alp ; i >= 0 ; i--)
	  if (s >= (1 << i)){
	  	y = spt[y][i];
	  	s -= (1 << i);
	  }
	
	return V[y - 1] - V[x - 1];
}

void solve(int n,int s){
	ll max_profit = 0;
	int start = 1;
	
	for (int i = 1 ; i <= n ; i++)
	  if (maximized(max_profit,profit(i,n,s)))
	      start = i;
	
	vector <int> lst;
	while (s > 0 && start <= n){
		lst.push_back(nxt[start]);
		
		start = nxt[nxt[start]] + 1;
		s--;
	}
	
	cout << lst.size() << "\n";
	for (int x : lst) cout << x << " ";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n,s;ll k;
	cin >> n >> s >> k;
	input(n,s,k);
	
	prepare(n,k);
	
	//k is not important, as exhausted using sparse table and nxt
	solve(n,s);

	return 0;
}

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