oj.uz

Submission #977747

# Submission time Handle Problem Language Result Execution time Memory
977747 2024-05-08T10:28:58 Z Requiem Building Bridges (CEOI17_building) C++17
100 / 100
 55 ms 71096 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "bbridge"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
int h[MAXN] , w[MAXN];
int prew[MAXN];
int n;

namespace subtask1{
    bool checkSubtask1(){
        return n <= 3000;
    }

    int sqr(int x){
        return x * x;
    }

    int dp[MAXN];
    void solveSubtask1(){
        memset(dp, 0x3f, sizeof(dp));
        dp[1] = 0;
        for(int i = 2; i <= n; i++){
            for(int j = i - 1; j >= 1; j--){
                minimize(dp[i], dp[j] + sqr(abs(h[i] - h[j])) + (prew[i - 1] - prew[j]) );
            }
        }

        cout << dp[n] << endl;
    }
}

namespace subtask2{
    bool checkSubtask2(){
         return true;
    }

    struct line{
         int a, b;
         long long val(int x){
             return a * x + b;
         }

         line(int a = 0, int b = 0): a(a), b(b) {}

         bool operator == (const line &other){
              return !(a == other.a and b == other.b);
         }
    };
    const int MAXH = 1e6 + 9;
    line lichao[MAXH << 2];
    long long dp[MAXN];

    void reset(){
         for(int i = 0; i < 4 * MAXH; i++){
             lichao[i] = {0, (int) 1e18};
         }
    }

    void update(int node, int l, int r, line cur){
         int mid = (l + r) >> 1;
         bool f1 = cur.val(l) <= lichao[node].val(l);
         bool f2 = cur.val(mid) <= lichao[node].val(mid);

         if (f2) swap(lichao[node], cur);
         if (r == l + 1) return;
         else if (f1 != f2) update(node << 1, l, mid, cur);
         else {
             update(node << 1 | 1, mid, r, cur);
         }
    }

    int get(int node, int l, int r, int pos){
        if (l == r - 1){
            return lichao[node].val(pos);
        }
        int mid = (l + r) >> 1;
        if (pos < mid) return min(lichao[node].val(pos), get(node << 1, l, mid, pos));
        else return min(lichao[node].val(pos), get(node << 1 | 1, mid, r, pos));
    }
    void solveSubtask2(){
        reset();
        dp[1] = 0;
        update(1, 0, 1e6, line(-2 * h[1], dp[1] + h[1] * h[1] - prew[1]));

//        cout << get(1, 0, 1e6, 39) << endl;
        for(int i = 2; i <= n; i++){
            dp[i] = get(1, 0, 1e6, h[i]) + prew[i - 1] + h[i] * h[i];
            update(1, 0, 1e6, line(-2 * h[i], dp[i] + h[i] * h[i] - prew[i]));
//            cout << dp[i] << ' ';
        }
        cout << dp[n] << endl;

    }
}
main()
{
    fast;
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
   }
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> h[i];
   }

   for(int i = 1; i <= n; i++){
       cin >> w[i];
       prew[i] = prew[i - 1] + w[i];
   }

//   if (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0;
   if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
**/

Compilation message

building.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main()
      | ^~~~
building.cpp: In function 'int main()':
building.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 67920 KB Output is correct
2 Correct 17 ms 69980 KB Output is correct
3 Correct 15 ms 67932 KB Output is correct
4 Correct 17 ms 68204 KB Output is correct
5 Correct 16 ms 68184 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 70800 KB Output is correct
2 Correct 49 ms 70876 KB Output is correct
3 Correct 49 ms 71096 KB Output is correct
4 Correct 48 ms 70740 KB Output is correct
5 Correct 45 ms 69460 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 67920 KB Output is correct
2 Correct 17 ms 69980 KB Output is correct
3 Correct 15 ms 67932 KB Output is correct
4 Correct 17 ms 68204 KB Output is correct
5 Correct 16 ms 68184 KB Output is correct
6 Correct 51 ms 70800 KB Output is correct
7 Correct 49 ms 70876 KB Output is correct
8 Correct 49 ms 71096 KB Output is correct
9 Correct 48 ms 70740 KB Output is correct
10 Correct 45 ms 69460 KB Output is correct
11 Correct 55 ms 68332 KB Output is correct
12 Correct 55 ms 69688 KB Output is correct
13 Correct 46 ms 68176 KB Output is correct
14 Correct 54 ms 69716 KB Output is correct
15 Correct 52 ms 69320 KB Output is correct
16 Correct 53 ms 67996 KB Output is correct
17 Correct 39 ms 69712 KB Output is correct
18 Correct 39 ms 69712 KB Output is correct