Submission #571227

#	Time	Username	Problem	Language	Result	Execution time	Memory
571227		YouAreMyGalaxy	Building Bridges (CEOI17_building)	C++17	100 / 100	152 ms	6588 KiB

building

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 1e5;
long long dp[N + 1], h[N + 1], w[N + 1], sumw;
int n;
struct ConvexHull
{
    vector<long double> inter;
    vector<int> line;
    void Clear()
    {
        inter.clear();
        line.clear();
    }
    long long A(int j)
    {
        return 2 * h[j];
    }
    long long B(int j)
    {
        return dp[j] + h[j] * h[j];
    }
    long long C(int i)
    {
        return h[i] * h[i] - w[i];
    }
    long double intersect(int i, int j)
    {
        return (long double)(B(j) - B(i))/(A(i) - A(j));
    }
    void add(int i)
    {
        while(inter.size() > 1 || (inter.size() == 1 && A(i) == A(line.back())))
        {
            if (A(i) == A(line.back()))
            {
                if (B(i) > B(line.back()))
                {
                    return ;
                }
                line.pop_back();
                inter.pop_back();
                continue;
            }
            if (intersect(i, line[line.size() - 2]) >= intersect(i, line.back()))
            {
                line.pop_back();
                inter.pop_back();
            }
            else
            {
                break;
            }
        }
        if (inter.empty())
        {
            inter.push_back(-1e18);
        }
        else
        {
            inter.push_back(intersect(i, line.back()));
        }
        line.push_back(i);
    }
    long long get(int i)
    {
        if (line.empty())
        {
            return 1e18;
        }
        int j = upper_bound(inter.begin(), inter.end(), (long double) -h[i]) - inter.begin() - 1;
        return A(line[j]) * -h[i] + B(line[j]) + C(i);
    }
} CHT[17];
void add(int i)
{
    vector<int> tmp = {i};
    int j = 0;
    while(!CHT[j].line.empty())
    {
        move(CHT[j].line.begin(), CHT[j].line.end(), back_inserter(tmp));
        CHT[j].Clear();
        ++j;
    }
    sort(tmp.begin(), tmp.end(), [&](const int &x, const int &y)
         {
             return h[x] > h[y];
         });
    for (int k : tmp)
    {
        CHT[j].add(k);
    }
}
long long get(int i)
{
    long long ret = 1e18;
    for (int j = 0; j <= 16; ++ j)
    {
        ret = min(ret, CHT[j].get(i));
    }
    return ret;
}
void read()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> h[i];
    }
    for (int i = 1; i <= n; ++ i)
    {
        cin >> w[i];
        sumw += w[i];
    }
}
void solve()
{
    dp[1] = -w[1];
    add(1);
    for (int i = 2; i <= n; ++ i)
    {
        dp[i] = get(i);
        add(i);
        //cerr << dp[i] << ' ';
    }
    cout << dp[n] + sumw;
}
int  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40