oj.uz

Submission #524297

# Submission time Handle Problem Language Result Execution time Memory
524297 2022-02-09T02:21:15 Z aadit_ambadkar Cover (COCI18_cover) C++17
120 / 120
 9 ms 444 KB 
/*
    This code belongs to Aadit Ambadkar
    Date: 2022-02-08 17:19:16
    Problem: cover
*/
#include <bits/stdc++.h>
using namespace::std;

typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define INF 2e18+10
#define FF first
#define SS second

int main() {
    fastio;
    int n; cin >> n;
    int ne[n+1];
    pair<ll, ll> pt[n+1];
    ll dp[n+1];
    memset(ne, 0, sizeof(ne));
    memset(dp, 0, sizeof(dp));
    FOR(i, 1, n+1) {
        cin >> pt[i].FF >> pt[i].SS;
        pt[i].FF = abs(pt[i].FF);
        pt[i].SS = abs(pt[i].SS);
    }
    sort(pt+1, pt+n+1);
    FOR(i, 1, n+1) {
        ne[i]=0;
        for (int j = i-1; j >= 1; j--) {
            if (pt[j].SS > pt[i].SS) {
                ne[i]=j;
                break;
            }
        }
    }
    // cout << "c1" << endl;
    FOR(i, 1, n+1) {
        dp[i]=INF;
    }
    // cout << "c2" << endl;
    // cout << n << endl;
    FOR(i, 1, n+1) {
        int at = i;
        // cout << "p" << i << endl;
        while (at != 0) {
            // cout << i << " " << at << endl;
            dp[i]=min(dp[i], 4LL*pt[i].FF*pt[at].SS+dp[ne[at]]);
            at=ne[at];
        }
        // cout << "c" << i << endl;
    }
    // FOR(i, 1, n) {
    //     cout << dp[i] << " ";
    // }
    cout << dp[n] << "\n";
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 9 ms 444 KB Output is correct