제출 #521615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521615		dsyz	Lasers (NOI19_lasers)	C++17	100 / 100	373 ms	68916 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
bool cmp(pair<ll,pair<ll,ll> > a,pair<ll,pair<ll,ll> > b){
	if(a.second.first == b.second.first){ //same row
		return a.second.second < b.second.second;
	}else{
		return a.first < b.first;
	}
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll L,R;
	cin>>L>>R;
	vector<ll> rows[R];
	ll maxlevel = 0;
	ll maximum = 0;
	ll prefix[R];
	ll suffix[R];
	memset(prefix,0,sizeof(prefix));
	memset(suffix,0,sizeof(suffix));
	for(ll i = 0;i < R;i++){
		ll X;
		cin>>X;
		maxlevel = max(maxlevel,X);
		ll cur = 0;
		for(ll j = 0;j < X;j++){
			ll a;
			cin>>a;
			cur += a;
			rows[i].push_back(a);
		}
		suffix[i] = L - cur;
		maximum = max(maximum,cur);
	}
	vector<pair<ll,pair<ll,ll> > > level; //level is the vertical thing, row is index
	for(ll i = 0;i < R;i++){
		ll total = 0;
		for(ll j = 0;j < rows[i].size();j++){
			total += rows[i][j];
			level.push_back(make_pair(total,make_pair(i,j)));
		}
	}
	sort(level.begin(),level.end(),cmp);
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	for(ll i = 0;i < R;i++){
		pq.push(make_pair(suffix[i],i));
	}
	ll sum = L;
	ll l = 0;
	ll r = L - maximum;
	ll prevr = 0;
	sum -= r - prevr;
	prevr = L - maximum;	
	for(ll i = 0;i < level.size();i++){
		prefix[level[i].second.first] += rows[level[i].second.first][level[i].second.second];
		l = max(l,prefix[level[i].second.first]);
		prevr = max(prevr,l);
		suffix[level[i].second.first] += rows[level[i].second.first][level[i].second.second];
		while(pq.size() != 0 && pq.top().first != suffix[pq.top().second]){
			ll a = suffix[pq.top().second];
			ll b = pq.top().second;
			pq.pop();
			pq.push(make_pair(a,b));
		}
		r = pq.top().first;
		sum -= max(0ll,r - prevr);
		prevr = max(prevr,r);
	}
	cout<<sum<<'\n';
}

컴파일 시 표준 에러 (stderr) 메시지

lasers.cpp: In function 'int main()':
lasers.cpp:40:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(ll j = 0;j < rows[i].size();j++){
      |                ~~^~~~~~~~~~~~~~~~
lasers.cpp:56:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(ll i = 0;i < level.size();i++){
      |               ~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13