oj.uz

Submission #530731

# Submission time Handle Problem Language Result Execution time Memory
530731 2022-02-26T15:30:13 Z Killer2501 Cover (COCI18_cover) C++14
120 / 120
 3 ms 864 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 5e3+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const int inf = 1e9;
int n, t, b[N][N], d[N], lab[N], c[N], a[N][N];
ll ans, tong, dp[N];
ll m, k;
pii p[N], start, finish;
vector<int> gx[N], gy[N];
vector<pii> vi;
string s[N];
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> p[i].fi >> p[i].se;
        p[i].fi = abs(p[i].fi);
        p[i].se = abs(p[i].se);
    }
    sort(p+1, p+1+n);
    for(int i = 1; i <= n; i ++)
    {
        while(!vi.empty() && vi.back().se <= p[i].se)vi.pop_back();
        vi.pb(p[i]);
    }
    for(int i = 1; i <= vi.size(); i ++)
    {
        dp[i] = 1ll * vi[0].se * vi[i-1].fi;
        for(int j = 1; j <= i; j ++)
        {
            dp[i] = min(dp[i], dp[j-1] + 1ll*vi[j-1].se * vi[i-1].fi);
        }
    }
    cout << dp[vi.size()]*4;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
    int test = 1;
    //cin >> test;
    while(test -- > 0)sol();
    return 0;
}

Compilation message

cover.cpp: In function 'void sol()':
cover.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 1; i <= vi.size(); i ++)
      |                    ~~^~~~~~~~~~~~
cover.cpp: In function 'int main()':
cover.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cover.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 1 ms 720 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 728 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 3 ms 864 KB Output is correct