Submission #1266072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266072		herominhsteve	Jobs (BOI24_jobs)	C++20	29 / 100	60 ms	25320 KiB

Main

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NAME"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 3e5 + 5;
const long long INF = (long long) 2e18 + 15092007;

int n;
long long S;
vector<pair<long long,int>> input;
vector<long long> w;
bool isLine=1;

void init(){
	cin>>n>>S;
	w.assign(n+1,0);
	input.resize(n+1);
	for (int i=1;i<=n;i++){
		int x;
		cin>>w[i]>>x;
		if (x and x!=i-1) isLine=0;
		input[i] = make_pair(w[i],x);
	}
}

namespace Line{
	vector<vector<long long>> chains;
	int numChains;
	void constructChains(){
		vector<long long> curChain;
		for (int i=1;i<=n;i++){
			if (!input[i].second and !curChain.empty()){
				chains.push_back(curChain);
				curChain.clear();
			}
			curChain.push_back({input[i].first});
		}
		if (!curChain.empty()) chains.push_back(curChain);
		numChains = chains.size();
	}
	
	struct Chain{
		long long req;
		long long gain;
		int ID;
		Chain(long long r,long long g,int id): req(r),gain(g),ID(id) {}
		bool operator < (const Chain &other) const{
			return req > other.req;
		}
	};

	priority_queue<Chain> pq;
	vector<int> ptr;
	
	bool getNextSegment(int ID,long long &req,long long &gain){
		long long minPre = INF;
		long long pre = 0;
		for (int &cid = ptr[ID];cid < (int)chains[ID].size();cid++){
			pre += chains[ID][cid];
			minimize(minPre,pre);
			if (pre>=0){
				req = max(0ll, -minPre);
				gain = pre;
				cid++;
				return true;
			}
		}
		return false;
	}

	void prepareRequirement(){
		for (int i=0;i<numChains;i++){
			long long req,gain;
			if (getNextSegment(i,req,gain)){
				pq.emplace(req,gain,i);
			}
		}
	}

	void solve(){
		constructChains();
		ptr.assign(numChains,0);
		prepareRequirement();
		long long totalGain=0;
		while (!pq.empty()){
			long long req = pq.top().req;
			long long gain = pq.top().gain;
			int ID = pq.top().ID;
			pq.pop();
			if (S + totalGain < req) break;
			else{
				totalGain += gain;
				if (getNextSegment(ID,req,gain)){
					pq.emplace(req,gain,ID);
				}
			}
		}
		cout<<totalGain;
		exit(0);
	}
};

void sol(){
	if (isLine) Line::solve();
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31