Submission #840041

#TimeUsernameProblemLanguageResultExecution timeMemory
840041cjoaClosing Time (IOI23_closing)C++17
0 / 100
1067 ms6492 KiB
#include "closing.h" #include <vector> #include <algorithm> #include <iostream> using namespace std; using llong = long long; const llong INF = 4e18; vector<llong> F(int N, const vector<int>& W, int src) { vector<llong> V(N + 1, INF); V[0] = V[1] = 0; llong sum_left = 0, sum_left2 = 0; for (int l = src; l >= 0; --l) { llong sum_right = 0, sum_right2 = 0; for (int r = src; r < N; ++r) { int len = r - l + 1; V[len] = min(V[len], sum_left2 + sum_right2); if (r+1 < N) { sum_right += W[r]; sum_right2 += sum_right; } } if (l > 0) { sum_left += W[l-1]; sum_left2 += sum_left; } } for (int len = N-1; len >= 1; len--) { if (V[len] > V[len+1]) V[len] = V[len+1]; } /* cerr << "src: " << src << endl; for (int len = 1; len <= N; len++) cerr << V[len] << ' '; cerr << endl; */ return V; } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { // subtasks 2, 3, and 4 // cerr << "K: " << K << endl; vector<llong> VX = F(N, W, X); vector<llong> VY = F(N, W, Y); int res = 0; for (int lenX = 1; lenX <= N and VX[lenX] <= K; lenX++) { auto it = upper_bound(VY.begin(), VY.end(), K - VX[lenX]); int lenY = it - VY.begin() - 1; // cerr << "lenX: " << lenX << " lenY: " << lenY << endl; res = max(res, lenX + lenY); } return res; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...