oj.uz

Submission #979585

# Submission time Handle Problem Language Result Execution time Memory
979585 2024-05-11T08:00:03 Z kilkuwu Boxes with souvenirs (IOI15_boxes) C++17
10 / 100
 1 ms 348 KB 
#include "boxes.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else 
#define dbg(...) ;
#define timer(...) ;
#endif

long long delivery(int N, int K, int L, int p[]) {
  int split = std::upper_bound(p, p + N, L / 2) - p;

  int left = split;
  int right = split;

  std::vector<long long> dp(N);

  for (int i = N - 1; i >= split; i--) {
    if (i + K < N) {
      dp[i] = dp[i + K] + (L - p[i]) * 2;
    } else {
      dp[i] = (L - p[i]) * 2;
    }
  }

  for (int i = 0; i < split; i++) {
    if (i - K >= 0) {
      dp[i] = dp[i - K] + p[i] * 2;
    } else {
      dp[i] = p[i] * 2;
    }
  }

  long long ans = split > 0 ? dp[split - 1] : 0;
  ans += (split < N) ? dp[split] : 0;
  long long round = 1e18;
  for (int i = split; i < N && i - K + 1 < split; i++) {
    long long cand = L;
    cand += split + 1 < N ? dp[split + 1] : 0;
    cand += i - K >= 0 ? dp[i - K] : 0;
    round = std::min(round, cand);
  }

  return std::min(ans, round);
}

#ifdef LOCAL

int main() {

  int N, K, L, i;
  std::cin >> N >> K >> L;

  int *p = (int*)malloc(sizeof(int) * (unsigned int)N);

  for (i = 0; i < N; i++) {
    std::cin >> p[i];
  }

  std::cout << delivery(N, K, L, p) << "\n";
  return 0;
}
#endif

Compilation message

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:13:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   13 |   int split = std::upper_bound(p, p + N, L / 2) - p;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
boxes.cpp:15:7: warning: unused variable 'left' [-Wunused-variable]
   15 |   int left = split;
      |       ^~~~
boxes.cpp:16:7: warning: unused variable 'right' [-Wunused-variable]
   16 |   int right = split;
      |       ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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