fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  5. #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
  6.  
  7. using ll = long long;
  8.  
  9. template<typename X, typename Y>
  10. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  11. template<typename X, typename Y>
  12. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  13.  
  14.  
  15. const int MAXN = 1e5 + 5;
  16. const ll INF = 1e18 + 67;
  17.  
  18. int N, A[MAXN], B[MAXN];
  19. ll X, Y, Z;
  20.  
  21. namespace Subtask1 {
  22.     bool check() {
  23.         return N == 2;
  24.     }
  25.     void solve() {
  26.         ll ans = 0;
  27.         FOR(i, 1, N) {
  28.             int M = min(A[i], B[i]);
  29.             A[i] -= M; B[i] -= M;
  30.             ans += (ll)A[i] * Y + (ll)B[i] * X;
  31.         }
  32.         if (X + Y > Z) {
  33.             ll D = A[1] > 0 ? min(A[1], B[2]) : min(A[2], B[1]);
  34.             ans += D * Z;
  35.             ans -= A[1] > 0 ? D * X : D * Y;
  36.             ans -= A[2] > 0 ? D * X : D * Y;
  37.         }
  38.         cout << ans << "\n";
  39.     }
  40. }
  41.  
  42. namespace Subtask2 {
  43.     bool check() {
  44.         return N <= 100;
  45.     }
  46.     void solve() {
  47.         vector<int> P, Q;
  48.         FOR(i, 1, N) {
  49.             FOR(k, 1, A[i]) P.push_back(i);
  50.             FOR(k, 1, B[i]) Q.push_back(i);
  51.         }
  52.         int nP = P.size(), nQ = Q.size();
  53.         vector<vector<ll>> dp(nP + 5, vector<ll>(nQ + 5, INF));
  54.         dp[0][0] = 0;
  55.         FOR(i, 0, nP) FOR(j, 0, nQ) {
  56.             if (dp[i][j] == INF) continue;
  57.             if (i < nP) chmin(dp[i + 1][j], dp[i][j] + Y);
  58.             if (j < nQ) chmin(dp[i][j + 1], dp[i][j] + X);
  59.             if (i < nP && j < nQ) chmin(dp[i + 1][j + 1], dp[i][j] + Z * abs(P[i] - Q[j]));
  60.         }
  61.         cout << dp[nP][nQ] << "\n";
  62.     }
  63. }
  64.  
  65. namespace Fulltask {
  66.     void solve() {
  67.         ll ans = 0;
  68.         priority_queue<ll> pqA, pqB;
  69.         FOR(i, 1, N) {
  70.             int M = min(A[i], B[i]);
  71.             A[i] -= M; B[i] -= M;
  72.             ans += (ll)A[i] * Y + (ll)B[i] * X;
  73.             ll C = (ll)i * Z;
  74.             while (A[i] > 0) {
  75.                 if (!pqB.empty() && pqB.top() - C > 0) {
  76.                     ll K = pqB.top(); pqB.pop();
  77.                     ans -= (K - C);
  78.                     pqA.push(X + Y + 2LL * C - K);
  79.                 } else pqA.push(X + Y + C);
  80.                 A[i]--;
  81.             }
  82.             while (B[i] > 0) {
  83.                 if (!pqA.empty() && pqA.top() - C > 0) {
  84.                     ll K = pqA.top(); pqA.pop();
  85.                     ans -= (K - C);
  86.                     pqB.push(X + Y + 2LL * C - K);
  87.                 } else pqB.push(X + Y + C);
  88.                 B[i]--;
  89.             }
  90.         }
  91.         cout << ans << "\n";
  92.     }
  93. }
  94.  
  95. void solve() {
  96.     cin >> N >> X >> Y >> Z;
  97.     FOR(i, 1, N) cin >> A[i] >> B[i];
  98.     if (Subtask1::check()) Subtask1::solve();
  99.     else if (Subtask2::check()) Subtask2::solve();
  100.     else Fulltask::solve();
  101. }
  102.  
  103. int main() {
  104.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  105.  
  106.     // freopen("GARDEN.INP", "r", stdin);
  107.     // freopen("GARDEN.OUT", "w", stdout);
  108.  
  109.     int tests = 1; // cin >> tests;
  110.     while (tests--) solve();
  111.  
  112.     #ifdef LOCAL
  113.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  114.     #endif
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
4 100 200 1
1 4
2 3
3 2
4 0
stdout
copy 
210
https://ideone.com/iCLALN
language:
C++14 (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!