제출 #838074

#제출 시각아이디문제언어결과실행 시간메모리
838074caganyanmaz카니발 티켓 (IOI20_tickets)C++17
11 / 100
27 ms30440 KiB
#include <bits/stdc++.h> #define pb push_back #define mp(x...) array<int, 2>({x}) #define int int64_t using namespace std; //#define DEBUGGING #ifdef DEBUGGING #include "../debug.h" #else #define debug(x...) void(42) #endif constexpr static int INF = 1e15; constexpr static int MXN = 1505; int prefix[MXN][MXN], suffix[MXN][MXN]; void allocate_tickets(vector<vector<int32_t>> s); int find_maximum(int32_t _k, vector<vector<int32_t>> x) { int k = _k; int n = x.size(); int m = x[0].size(); vector<vector<array<int, 2>>> dp(n+1, vector<array<int,2>>((k*n/2)+1, mp(-INF, -1))); dp[0][0] = {0, -1}; for (int i = 0; i < n; i++) { for (int j = 1; j <= m; j++) prefix[i][j] = prefix[i][j-1] + x[i][j-1]; for (int j = m-1; j >= 0; j--) suffix[i][j] = suffix[i][j+1] + x[i][j]; for (int j = 0; j <= k*n/2; j++) for (int l = 0; l <= min(j, k); l++) dp[i+1][j] = max(dp[i+1][j], mp(dp[i][j-l][0] - prefix[i][l] + suffix[i][l-k+m], l)); } debug(dp.size(), n, dp[0].size(), k*n/2); int current_count = k*n/2; vector<vector<int32_t>> s(n, vector<int32_t>(m,-1)); vector<array<int, 2>> bounds; // Left right debug("a"); vector<array<int, 2>> counts; // Small count, n for (int i = n-1; i >= 0; i--) { debug(i); int current_val = dp[i+1][current_count][1]; counts.pb({current_val, i}); current_count -= current_val; debug(i, current_count); bounds.pb({0, m-1}); } for (int i = 0; i < k; i++) { for (int j = n/2; j < n; j++) { s[counts[j][1]][bounds[counts[j][1]][1]--] = i; counts[j][0]--; } for (int j = 0; j < n/2; j++) { s[counts[j][1]][bounds[counts[j][1]][0]++] = i; } sort(counts.begin(), counts.end()); } debug("b"); allocate_tickets(s); return dp[n][k*n/2][0]; }
#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...