oj.uz

Submission #571227

# Submission time Handle Problem Language Result Execution time Memory
571227 2022-06-01T15:15:17 Z YouAreMyGalaxy Building Bridges (CEOI17_building) C++17
100 / 100
 152 ms 6588 KB 
//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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 4028 KB Output is correct
2 Correct 113 ms 3916 KB Output is correct
3 Correct 118 ms 3936 KB Output is correct
4 Correct 130 ms 3652 KB Output is correct
5 Correct 85 ms 4608 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 118 ms 4028 KB Output is correct
7 Correct 113 ms 3916 KB Output is correct
8 Correct 118 ms 3936 KB Output is correct
9 Correct 130 ms 3652 KB Output is correct
10 Correct 85 ms 4608 KB Output is correct
11 Correct 131 ms 3964 KB Output is correct
12 Correct 152 ms 3948 KB Output is correct
13 Correct 69 ms 3744 KB Output is correct
14 Correct 120 ms 4028 KB Output is correct
15 Correct 74 ms 6588 KB Output is correct
16 Correct 59 ms 4628 KB Output is correct
17 Correct 35 ms 3612 KB Output is correct
18 Correct 34 ms 3648 KB Output is correct