Submission #1089726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089726		quangminh412	Garaža (COCI17_garaza)	C++14	0 / 160	684 ms	196540 KiB

garaza

#include <bits/stdc++.h>
using namespace std;

/*
  John Watson

  Mua Code nhu mua Florentino !!
*/

#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

const int oo = 1e9;
const int maxn = 2e5 + 9;

struct Query
{
	int l, r;
	
	Query() = default;
	Query(int l, int r) : l(l), r(r) {}
	
	bool operator < (Query &other)
	{
		if (r == other.r) return l < other.l;
		return r < other.r;
	}
};

int n, q;
int b[maxn], pre[maxn];
vector<Query> queries;

int segment(int l, int r) { return pre[r] - pre[l - 1]; }

signed main()
{
	if (fopen("NRE.INP", "r"))
	{
		freopen("NRE.INP", "r", stdin);
		freopen("NRE.OUT", "w", stdout);
	}
	faster();

	cin >> n;
	for (int i = 1; i <= n; i++) 
	{
		cin >> b[i];
		pre[i] = (b[i] == 0) + pre[i - 1];
	}
	cin >> q;
	while (q--)
	{
		int l, r; cin >> l >> r;
		queries.push_back(Query(l, r));
	}
	sort(queries.begin(), queries.end());
	vector<int> dp(n + 5, oo);
	dp[0] = 0;
	
	q = queries.size();
	int cur = 0;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = (0 != b[i]) + dp[i - 1];
		while (cur < q && queries[cur].r < i) cur++;
		if (cur == q || queries[cur].r > i)
			continue;
			
		while (cur < q && queries[cur].r == i)
		{
			int l = queries[cur].l;
			int r = queries[cur].r;
			dp[i] = min(dp[i], dp[l - 1] + segment(l, r));
			cur++;
		}
	}
	
	cout << dp[n] << '\n';

	return 0;
}

Compilation message (stderr)

garaza.cpp: In function 'int main()':
garaza.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   freopen("NRE.INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   freopen("NRE.OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 40
• Subtask 4: 0 / 40