답안 #222219

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222219 2020-04-12T11:30:39 Z ZwariowanyMarcin Cover (COCI18_cover) C++17
120 / 120
8 ms 512 KB
#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

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);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 384 KB Output is correct
10 Correct 8 ms 512 KB Output is correct