답안 #1108781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108781	2024-11-05T04:03:09 Z	KasymK	나일강 (IOI24_nile)	C++17	67 / 100	2000 ms	12624 KB

nile

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 1e5+5;
const ll INF = 1e18;
array<int, 3> v[N];
ll dp[N], p[N];
struct node {
    int l, r;
    ll val;
} seg[N<<2];

void build(int x, int l, int r){
    seg[x].l = l, seg[x].r = r;
    if(l==r){
        seg[x].val = INF;
        return;
    }
    int mid = (l+r)>>1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    seg[x].val = min(seg[x<<1].val, seg[x<<1|1].val);
}

void update(int x, int k, ll u){
    if(seg[x].l==seg[x].r){
        seg[x].val = u;
        return;
    }
    int mid = (seg[x].l+seg[x].r)>>1;
    if(k<=mid)
        update(x<<1, k, u);
    else
        update(x<<1|1, k, u);
    seg[x].val = min(seg[x<<1].val, seg[x<<1|1].val);
}

ll query(int x, int l, int r){
    if(l>r)
        return INF;
    if(seg[x].l==l and seg[x].r==r)
        return seg[x].val;
    int mid = (seg[x].l+seg[x].r)>>1;
    if(r <= mid)
        return query(x<<1, l, r);
    else if(l > mid)
        return query(x<<1|1, l, r);
    else
        return min(query(x<<1, l, mid), query(x<<1|1, mid+1, r));
}

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
    int n = (int)W.size();
    for(int i = 1; i <= n; ++i)
        v[i][0] = W[i-1], v[i][1] = A[i-1], v[i][2] = B[i-1];
    sort(v+1, v+n+1);
    for(int i = 1; i <= n; ++i)
        p[i] = p[i-1]+v[i][1];
    vector<ll> ans;
    build(1, 1, n);
    for(int &d : E){
        for(int i = 1; i <= n; ++i)
            dp[i] = INF;
        dp[0] = 0;
        int l = 1;
        for(int i = 1; i <= n; ++i){
            while(l<=n and v[i][0]-v[l][0]>d)
                l++;
            dp[i] = dp[i-1]+v[i][1];
            umin(dp[i], query(1, l, i-1)+v[i][2]+p[i-1]);
            update(1, i, dp[i-1]+v[i][2]-p[i]);
        }
        ans.pb(dp[n]);
    }
    return ans;
}

Subtask #0
0.0 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2384 KB	Output is correct

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2640 KB	Output is correct
2	Correct	3 ms	2640 KB	Output is correct
3	Correct	3 ms	2640 KB	Output is correct
4	Correct	3 ms	2640 KB	Output is correct
5	Correct	3 ms	2640 KB	Output is correct
6	Correct	3 ms	2516 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	111 ms	12104 KB	Output is correct
2	Correct	113 ms	12116 KB	Output is correct
3	Correct	111 ms	12120 KB	Output is correct
4	Correct	110 ms	11224 KB	Output is correct
5	Correct	109 ms	12112 KB	Output is correct
6	Correct	117 ms	12296 KB	Output is correct

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	10832 KB	Output is correct
2	Correct	121 ms	11088 KB	Output is correct
3	Correct	108 ms	11176 KB	Output is correct
4	Correct	107 ms	10924 KB	Output is correct
5	Correct	111 ms	10668 KB	Output is correct
6	Correct	102 ms	10920 KB	Output is correct

Subtask #4
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2640 KB	Output is correct
2	Correct	3 ms	2640 KB	Output is correct
3	Correct	3 ms	2640 KB	Output is correct
4	Correct	3 ms	2640 KB	Output is correct
5	Correct	3 ms	2640 KB	Output is correct
6	Correct	3 ms	2516 KB	Output is correct
7	Correct	3 ms	2640 KB	Output is correct
8	Correct	3 ms	2640 KB	Output is correct
9	Correct	3 ms	2640 KB	Output is correct
10	Correct	3 ms	2752 KB	Output is correct
11	Correct	3 ms	2640 KB	Output is correct
12	Correct	3 ms	2640 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2640 KB	Output is correct
2	Correct	3 ms	2640 KB	Output is correct
3	Correct	3 ms	2640 KB	Output is correct
4	Correct	3 ms	2640 KB	Output is correct
5	Correct	3 ms	2640 KB	Output is correct
6	Correct	3 ms	2516 KB	Output is correct
7	Correct	111 ms	12104 KB	Output is correct
8	Correct	113 ms	12116 KB	Output is correct
9	Correct	111 ms	12120 KB	Output is correct
10	Correct	110 ms	11224 KB	Output is correct
11	Correct	109 ms	12112 KB	Output is correct
12	Correct	117 ms	12296 KB	Output is correct
13	Correct	122 ms	10832 KB	Output is correct
14	Correct	121 ms	11088 KB	Output is correct
15	Correct	108 ms	11176 KB	Output is correct
16	Correct	107 ms	10924 KB	Output is correct
17	Correct	111 ms	10668 KB	Output is correct
18	Correct	102 ms	10920 KB	Output is correct
19	Correct	3 ms	2640 KB	Output is correct
20	Correct	3 ms	2640 KB	Output is correct
21	Correct	3 ms	2640 KB	Output is correct
22	Correct	3 ms	2752 KB	Output is correct
23	Correct	3 ms	2640 KB	Output is correct
24	Correct	3 ms	2640 KB	Output is correct
25	Correct	116 ms	12104 KB	Output is correct
26	Correct	137 ms	12480 KB	Output is correct
27	Correct	112 ms	12624 KB	Output is correct
28	Correct	105 ms	12492 KB	Output is correct
29	Correct	105 ms	12360 KB	Output is correct
30	Correct	96 ms	12272 KB	Output is correct

Subtask #6
0.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	122 ms	10832 KB	Output is correct
2	Correct	121 ms	11088 KB	Output is correct
3	Correct	108 ms	11176 KB	Output is correct
4	Correct	107 ms	10924 KB	Output is correct
5	Correct	111 ms	10668 KB	Output is correct
6	Correct	102 ms	10920 KB	Output is correct
7	Execution timed out	2055 ms	12104 KB	Time limit exceeded
8	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2384 KB	Output is correct
2	Correct	3 ms	2640 KB	Output is correct
3	Correct	3 ms	2640 KB	Output is correct
4	Correct	3 ms	2640 KB	Output is correct
5	Correct	3 ms	2640 KB	Output is correct
6	Correct	3 ms	2640 KB	Output is correct
7	Correct	3 ms	2516 KB	Output is correct
8	Correct	111 ms	12104 KB	Output is correct
9	Correct	113 ms	12116 KB	Output is correct
10	Correct	111 ms	12120 KB	Output is correct
11	Correct	110 ms	11224 KB	Output is correct
12	Correct	109 ms	12112 KB	Output is correct
13	Correct	117 ms	12296 KB	Output is correct
14	Correct	122 ms	10832 KB	Output is correct
15	Correct	121 ms	11088 KB	Output is correct
16	Correct	108 ms	11176 KB	Output is correct
17	Correct	107 ms	10924 KB	Output is correct
18	Correct	111 ms	10668 KB	Output is correct
19	Correct	102 ms	10920 KB	Output is correct
20	Correct	3 ms	2640 KB	Output is correct
21	Correct	3 ms	2640 KB	Output is correct
22	Correct	3 ms	2640 KB	Output is correct
23	Correct	3 ms	2752 KB	Output is correct
24	Correct	3 ms	2640 KB	Output is correct
25	Correct	3 ms	2640 KB	Output is correct
26	Correct	116 ms	12104 KB	Output is correct
27	Correct	137 ms	12480 KB	Output is correct
28	Correct	112 ms	12624 KB	Output is correct
29	Correct	105 ms	12492 KB	Output is correct
30	Correct	105 ms	12360 KB	Output is correct
31	Correct	96 ms	12272 KB	Output is correct
32	Execution timed out	2055 ms	12104 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-

답안 #1108781

Compilation message