Submission #544659

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
544659	2022-04-02 14:16:47	pokmui9909	수족관 1 (KOI13_aqua1)	C++17	100 / 100	5 ms	596 KiB

aqua1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define x first
#define y second
struct Data{
    ll l, r, w, t;
    bool operator < (const Data &t) const{
        if(l != t.l) return l < t.l;
        else return r < t.r;
    }
};
ll N, K, M;
pair<ll, ll> P[5005];
Data V[5005];
ll ans = 0;
 
void dnc(ll l, ll r, ll s){
    if(l > r) return;
    ll mn = 1e9, idx = 0;
    ll ok = 0;
    for(int i = l; i <= r; i++){
        if(mn > V[i].w) mn = V[i].w, idx = i;
        if(V[i].t == 1) ok = 1;
    }
    if(ok){
        ans -= (mn - s) * (V[r].r - V[l].l);
        dnc(l, idx - 1, mn);
        dnc(idx + 1, r, mn);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 23 / 23
• Subtask 2: 19 / 19
• Subtask 3: 22 / 22
• Subtask 4: 36 / 36