oj.uz

Submission #1099769

# Submission time Handle Problem Language Result Execution time Memory
1099769 2024-10-12T05:13:45 Z model_code Nile (IOI24_nile) C++17
23 / 100
 2000 ms 5716 KB 
// incorrect/zsolt_q1_heuristic.cpp

#include "nile.h"

#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
using ll = long long;
using pii = pair<int,int>;

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = (int)W.size();
    vector<pii> ord(N);
    for (int i = 0; i < N; ++i)
        ord[i] = {W[i], i};
    sort(ord.begin(), ord.end());
    vector<int> w(N), a(N), b(N);
    for (int i = 0; i < N; ++i) {
        int j = ord[i].second;
        w[i] = W[j], a[i] = A[j], b[i] = B[j];
    }
    vector<ll>v;
    for(int curq = 0; curq < E.size(); ++curq)
    {
        int D = E[curq];
        ll ans = 0ll;
        for (int i = 0; i < N;) {
            ans += b[i];
            int j = i+1, worst = a[i] - b[i];
            for (; j < N; ++j) {
                if (w[j] - w[j-1] > D)
                    break;
                ans += b[j];
                worst = min(worst, a[j] - b[j]);
            }
            if ((j - i) % 2 == 1)
                ans += worst;
            i = j;
        }
        v.push_back(ans);
    }
    return v;
}

Compilation message

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:25:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int curq = 0; curq < E.size(); ++curq)
      |                       ~~~~~^~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 4692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4596 KB Output is correct
2 Correct 24 ms 4696 KB Output is correct
3 Correct 28 ms 4680 KB Output is correct
4 Correct 26 ms 4692 KB Output is correct
5 Correct 26 ms 4696 KB Output is correct
6 Correct 31 ms 4700 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Incorrect 24 ms 4692 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4596 KB Output is correct
2 Correct 24 ms 4696 KB Output is correct
3 Correct 28 ms 4680 KB Output is correct
4 Correct 26 ms 4692 KB Output is correct
5 Correct 26 ms 4696 KB Output is correct
6 Correct 31 ms 4700 KB Output is correct
7 Execution timed out 2056 ms 5716 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 24 ms 4692 KB Output isn't correct
9 Halted 0 ms 0 KB -