Submission #1108498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108498		KasymK	Nile (IOI24_nile)	C++17	17 / 100	2048 ms	7912 KiB

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];

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;
    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];
            for(int j = l; j < i; ++j)
                umin(dp[i], dp[j-1]+v[i][2]+v[j][2]+p[i-1]-p[j]);
        }
        ans.pb(dp[n]);
    }
    return ans;
}

// int main(){
//     int n;
//     scanf("%d", &n);
//     vector<int> W, A, B;
//     for(int i = 1; i <= n; ++i){
//         int a, b, c;
//         scanf("%d%d%d", &a, &b, &c);
//         W.pb(a), A.pb(b), B.pb(c);
//     }
//     int q;
//     scanf("%d", &q);
//     vector<int> E;
//     while(q--){
//         int x;
//         scanf("%d", &x);
//         E.pb(x);
//     }
//     vector<ll> ans = calculate_costs(W, A, B, E);
//     for(auto i : ans)
//         printf("%lld ", i);
//     puts("");
// }

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 11 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18