Submission #1082411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082411		ZeroCool	Jobs (BOI24_jobs)	C++14	0 / 100	36 ms	5192 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int MOD = 1e9 + 7;
const int INF = 1e9;

const int N = 2e5  + 20;
const int LOG = 20;

ar<int, 2> get(stack<int> &s){
	int sum = 0;
	int mn = INF;
	int mx = 0;
	while(sum <= 0 && s.size()){
		sum += s.top();
		s.pop();
		mn = min(mn, sum);
		mx = max(mx, sum);
	}
	if(sum <= 0)return {-1, -1};
	return {mx - mn, sum};
}

void reverse(stack<int> &s){
	stack<int> v;
	while(s.size()){
		v.push(s.top());
		s.pop();
	}
	s = v;
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	int n , s;
	cin>>n>>s;
	int o = s;
	vector<stack<int> > v;
	priority_queue<ar<int, 3> > pq;
	for(int i = 0;i < n;i++){
		int p, x;
		cin>>x>>p;
		if(p == 0)v.push_back(stack<int>());
		v.back().push(x);
	}
	for(auto &u: v)reverse(u);
	for(int i = 0;i < v.size();i++){
		ar<int,2> a = get(v[i]);
		if(a[0] == -1)continue;
		pq.push({a[0], a[1], i});
	}
	while(pq.size()){
		ar<int, 3> a = pq.top();
		pq.pop();
		if(s + a[0] < 0)break;
		s += a[1];
		ar<int,2> b = get(v[a[2]]);
		if(b[0] != -1)pq.push({b[0], b[1], a[2]});
	}
	cout<<s - o;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::stack<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0;i < v.size();i++){
      |                ~~^~~~~~~~~~

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