oj.uz

답안 #743071

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743071 2023-05-17T07:44:58 Z Mauve 사탕 분배 (IOI21_candies) C++17
3 / 100
 5000 ms 31308 KB 
#include "candies.h"

#include <algorithm>
#include <vector>

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  int n = c.size(), q = v.size();
  std::vector<std::vector<std::pair<int, int>>> queriesL(n), queriesR(n);
  for (int i = 0; i < q; ++i) {
    queriesL[l[i]].emplace_back(i, v[i]);
    queriesR[r[i]].emplace_back(i, v[i]);
  }

  std::vector<int> s(n), vals(q);
  for (int i = 0; i < n; ++i) {
    for (auto [idx, val] : queriesL[i]) {
      vals[idx] = -val;
    }

    int mini = 0, maxi = 0, sum = 0, idx = 0;
    for (int j = q - 1; j >= 0; --j) {
      sum += vals[j];
      mini = std::min(mini, sum);
      maxi = std::max(maxi, sum);
      if (maxi - mini > c[i]) {
        idx = j;
        break;
      }
    }

    if (maxi - mini <= c[i]) {
      s[i] = -mini;
    } else {
      if (vals[idx] < 0) {
        s[i] = c[i] - maxi;
      } else {
        s[i] = -mini;
      }
    }

    for (auto [idx, val] : queriesR[i]) {
      vals[idx] = 0;
    }
  }

  return s;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1745 ms 29560 KB Output is correct
2 Execution timed out 5047 ms 29500 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 638 ms 14440 KB Output is correct
3 Correct 884 ms 14400 KB Output is correct
4 Execution timed out 5009 ms 31308 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 184 ms 11560 KB Output is correct
4 Correct 212 ms 13344 KB Output is correct
5 Execution timed out 5009 ms 24112 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 280 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 1745 ms 29560 KB Output is correct
7 Execution timed out 5047 ms 29500 KB Time limit exceeded
8 Halted 0 ms 0 KB -