Submission #720128

#TimeUsernameProblemLanguageResultExecution timeMemory
720128CyanmondLasers (NOI19_lasers)C++17
100 / 100
542 ms36648 KiB
#include <bits/stdc++.h> using i64 = long long; void solve() { int L, R; std::cin >> L >> R; std::map<int, int> stamps; while (R--) { int X; std::cin >> X; std::vector<int> W(X); for (auto &e : W) std::cin >> e; std::vector<int> sumW(X + 1); for (int i = 0; i < X; ++i) sumW[i + 1] = sumW[i] + W[i]; auto calcSum = [&](int l, int r) { return sumW[r] - sumW[l]; }; std::map<int, int> rls; for (int i = 0; i <= X; ++i) { const auto l = calcSum(0, i), r = L - calcSum(i, X); ++rls[l]; --rls[r]; } int val = 0, lastPos = 0; for (const auto &[p, v] : rls) { if (val == 0) { ++stamps[lastPos]; --stamps[p]; } val += v; lastPos = p; } } int val = 0, lastPos = 0, answer = 0; for (const auto &[p, v] : stamps) { if (val != 0) answer += p - lastPos; val += v; lastPos = p; } std::cout << answer << std::endl; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...