Submission #222219

#	Time	Username	Problem	Language	Result	Execution time	Memory
222219		ZwariowanyMarcin	Cover (COCI18_cover)	C++17	120 / 120	8 ms	512 KiB

cover

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
 
using namespace std;

const int nax = 5005;	
	
int n;
pair <int, int> t[nax];
ll dp[nax];
vector <pair<int, int>> v;

int main() {		
	scanf ("%d", &n);
	rep(i, 0, n - 1) {
		scanf ("%d%d", &t[i].fi, &t[i].se);
		if (t[i].fi < 0) t[i].fi *= -1;
		if (t[i].se < 0) t[i].se *= -1;
	}
	sort(t, t + n);
	int a = -1e9;
	per(i, 0, n - 1) {
		if (t[i].se > a) v.pb(t[i]);
		a = max(a, t[i].se);
	}
	v.pb({-1, -1});
	reverse(all(v));
	dp[0] = 0;
	rep(i, 1, ss(v) - 1) {
		dp[i] = 1e18;
		rep(j, 0, i - 1) {
			dp[i] = min(dp[i], dp[j] + (ll) v[i].fi * v[j + 1].se);
		}
	}
	printf ("%lld\n", 4 * dp[ss(v) - 1]);
		
		
	
	
	return 0;
}

Compilation message (stderr)

cover.cpp: In function 'int main()':
cover.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
cover.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &t[i].fi, &t[i].se);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120