Submission #1266063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266063		herominhsteve	Jobs (BOI24_jobs)	C++20	0 / 100	39 ms	12200 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 numChain;
	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);
		numChain = chains.size();
	}
	struct Chain{
		long long req;
		long long gain;
		Chain(long long r,long long g): req(r),gain(g) {}
		bool operator < (const Chain &other) const{
			return req > other.req;
		}
	};
	priority_queue<Chain> pq;
	void prepareRequirement(){
		for (vector<long long> v : chains){
			long long pre=0;
			long long minPre = INF;
			for (long long x : v){
				pre+=x;
				minimize(minPre,pre);
				if (pre>=0) break;
			}
			long long req = max(0ll, -minPre);
			long long gain=-INF;
			pre=0;
			for (long long x : v){
				pre+=x;
				maximize(gain,pre);
			}
			pq.emplace(req,gain);
		}
	}
	void solve(){
		constructChains();
		prepareRequirement();
		long long totalGain=0;
		long long res = 0;
		while (!pq.empty()){
			long long req = pq.top().req;
			long long gain = pq.top().gain;
			pq.pop();
			if (S + totalGain >= req) totalGain+=gain, maximize(res,totalGain);
			else break;
		}
		cout<<res;
		exit(0);
	}
};

void sol(){
	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: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31