oj.uz

Submission #1082372

# Submission time Handle Problem Language Result Execution time Memory
1082372 2024-08-31T08:36:49 Z vjudge1 Cover (COCI18_cover) C++17
48 / 120
 14 ms 604 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
#define dbg(v)  cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using pld = pair <ld,ld>;
const char el ='\n';
const char sp = ' ';
const int maxn = 2e5+5, mod = 1e9+7, N = 10;
const ll inf = 1e18L+3;
int n;
pii a[maxn];
ll dp[maxn];

bool cmp(pii x, pii y)
{
    if(x.ff!=y.ff)  return x.ff<y.ff;
    return x.ss>y.ss;
}

void input()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i].ff>>a[i].ss;
        a[i].ff = abs(a[i].ff);
        a[i].ss = abs(a[i].ss);
    }
    sort(a+1,a+n+1,cmp);
//    for(int i=1;i<=n;++i)   cout<<a[i]<<el;
}

void solve()
{
    fill(dp+1,dp+n+1,inf);
    dp[1] = a[1].ff*a[1].ss;
    for(int i=2;i<=n;++i)
    {
        int mx = a[i].ss;
        for(int j=i;j>0;--j)
        {
            mx = max(mx,a[j].ss);
            dp[i] = min(dp[i],dp[j-1]+mx*a[i].ff);
        }
    }
    cout<<dp[n]*4;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
//    cin>>test;
    while(test-->0)
    {
        input();
        solve();
    }
    return 0;
}

Subtask #1
48.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 6 ms 348 KB Output isn't correct
10 Incorrect 14 ms 604 KB Output isn't correct