oj.uz

Submission #1108498

# Submission time Handle Problem Language Result Execution time Memory
1108498 2024-11-04T09:17:35 Z KasymK Nile (IOI24_nile) C++17
17 / 100
 2000 ms 7912 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2384 KB Output is correct
2 Correct 12 ms 2384 KB Output is correct
3 Correct 12 ms 2384 KB Output is correct
4 Correct 12 ms 2384 KB Output is correct
5 Correct 13 ms 2600 KB Output is correct
6 Correct 12 ms 2384 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 7912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 6480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2384 KB Output is correct
2 Correct 12 ms 2384 KB Output is correct
3 Correct 12 ms 2384 KB Output is correct
4 Correct 12 ms 2384 KB Output is correct
5 Correct 13 ms 2600 KB Output is correct
6 Correct 12 ms 2384 KB Output is correct
7 Correct 4 ms 2384 KB Output is correct
8 Correct 4 ms 2384 KB Output is correct
9 Correct 4 ms 2612 KB Output is correct
10 Correct 4 ms 2384 KB Output is correct
11 Correct 5 ms 2384 KB Output is correct
12 Correct 4 ms 2384 KB Output is correct

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2384 KB Output is correct
2 Correct 12 ms 2384 KB Output is correct
3 Correct 12 ms 2384 KB Output is correct
4 Correct 12 ms 2384 KB Output is correct
5 Correct 13 ms 2600 KB Output is correct
6 Correct 12 ms 2384 KB Output is correct
7 Execution timed out 2048 ms 7912 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 6480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 12 ms 2384 KB Output is correct
3 Correct 12 ms 2384 KB Output is correct
4 Correct 12 ms 2384 KB Output is correct
5 Correct 12 ms 2384 KB Output is correct
6 Correct 13 ms 2600 KB Output is correct
7 Correct 12 ms 2384 KB Output is correct
8 Execution timed out 2048 ms 7912 KB Time limit exceeded
9 Halted 0 ms 0 KB -