Submission #524296

#	Time	Username	Problem	Language	Result	Execution time	Memory
524296		aadit_ambadkar	Cover (COCI18_cover)	C++11	120 / 120	10 ms	512 KiB

cover

/*
    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 / 120