Submission #575900

#	Time	Username	Problem	Language	Result	Execution time	Memory
575900		d4xn	Mountains (IOI17_mountains)	C++17	0 / 100	1 ms	300 KiB

mountains

#pragma GCC optimize ("Ofast")
#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
     
#define ld long double
#define ll long long
     
const int N = 2002;
     
int n, ans;
vector<pair<int, int>> sorted, taken;      
 
bool cmp(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
}

int maximum_deevs(vector<int> y) {
  ans = 0;
	n = y.size();
	sorted.resize(n);
  for(int i = 0; i < n; i++) {
		sorted[i] = make_pair(i, y[i]);
  }
  sort(sorted.begin(), sorted.end(), cmp);

  for(int i = 0; i < n; i++) {
    bool ok = 1;
    for (int j = 0; j < taken.size() && ok; j++) {
      // comprobar si se puede coger
			bool can = 0;
			int l = min(sorted[i].first, taken[j].first) + 1;
			int r = max(sorted[i].first, taken[j].first) - 1;
			while (l <= r) {
				ld a, b, c, d, e, f;
				a = sorted[i].first;
				b = sorted[i].second;
				c = taken[j].first;
				d = taken[j].second;
				e = l;
				f = y[l];
				if (sorted[i].first > taken[j].first) {
					swap(a, c);
					swap(b, d);
				}
				ld p = (d-b) / (c-a);
				ld h = b + ((e-a) * p);

				if (f > h) {
					can = 1;
					break;
				}
				l++;
			}
			if (!can) ok = 0;
    }
    if (ok) taken.push_back(sorted[i]);
  }

	int sz = taken.size();
  return max(sz, 1);
}

Compilation message (stderr)

mountains.cpp: In function 'int maximum_deevs(std::vector<int>)':
mountains.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int j = 0; j < taken.size() && ok; j++) {
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30