Submission #369275

#	Time	Username	Problem	Language	Result	Execution time	Memory
369275		Berted	Lasers (NOI19_lasers)	C++14	100 / 100	137 ms	10264 KiB

lasers

#include <iostream>
#include <algorithm>
#include <vector>
#define pii pair<int,int>
#define fst first
#define snd second
using namespace std;
int k,n,x,dt[500001]={};
vector<pii> v;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>k>>n;
	for (int i=0;i<n;i++)
	{
		int l = 0,r = k;
		cin>>x;
		for (int j=0;j<x;j++)
		{
			cin>>dt[j];l+=dt[j];
		}
		l-=dt[x-1];
		for (int j=x-1;j>=0;j--)
		{
			int l1 = l,r1 = l+dt[j],r2 = r,l2 = r-dt[j];
			//cout<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
			if (max(l1,l2)<min(r1,r2)) 
			{
				v.push_back({max(l1,l2),min(r1,r2)});
			}
			if (j) {l-=dt[j-1];}
			r-=dt[j];
		}
	}
	sort(v.begin(),v.end());
	int rs = 0,l = -1,r = -1;
	for (int i=0;i<v.size();i++)
	{
		if (r<v[i].fst) {rs += r-l;l = v[i].fst;r = v[i].fst;}
		r = max(r,v[i].snd);
	}
	rs += r-l;
	cout<<rs<<"\n";
	return 0;
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i=0;i<v.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