제출 #1122359

#제출 시각아이디문제언어결과실행 시간메모리
1122359osmanaySnowball (JOI21_ho_t2)C++14
0 / 100
1 ms336 KiB
//Snowball, OJ. Intervals problem. //Osman Ay, November 2024. #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, Q; cin >> N >> Q; vector<long long> X(N + 1); for (int i = 1; i <= N; i++) cin >> X[i]; vector<long long> W(Q + 1); vector<long long> preSum(Q + 1, 0), bestSum(Q+1, 0), maxL(Q + 1, 0), minR(Q + 1, 0); for(int i=1; i<=Q; i++) { cin >> W[i]; preSum[i] = preSum[i - 1] + W[i]; maxL[i] = max(maxL[i-1], preSum[i]); minR[i] = min(minR[i-1], preSum[i]); bestSum[i] = maxL[i] - minR[i]; } if (N == 0) cout << maxL[Q] - minR[Q] << endl; else { vector<long long> res(N + 1, 0); res[1] = -minR[Q]; res[N] = maxL[Q]; for (int i = 1; i <= N - 1; i++) { int len = X[i + 1] - X[i]; if (len >= maxL[Q] - minR[Q]) { res[i] += maxL[Q]; res[i + 1] += -minR[Q]; continue; } int j = upper_bound(bestSum.begin(), bestSum.end(), len) - bestSum.begin(); j--; res[i] += maxL[j]; res[i + 1] += -minR[j]; int diff = len - (maxL[j] - minR[j]); if (j < N && diff > 0) { if (W[j + 1] > 0) res[i] += diff; else res[i + 1] += diff; } } for (int i = 1; i <= N; i++) cout << res[i] << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...