fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. // Używamy stałej do oznaczania nieskończoności dla porównań min/max
  9. const int INF = 1e9;
  10.  
  11. int main() {
  12.     // Optymalizacja wejścia/wyjścia (dla dużych danych)
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(NULL);
  15.  
  16.     int n, m;
  17.     if (!(cin >> n >> m)) return 0;
  18.  
  19.     vector<int> A(n);
  20.     vector<int> B(m);
  21.  
  22.     // Wczytanie stosu 1 (od spodu do góry)
  23.     for (int i = 0; i < n; i++) cin >> A[i];
  24.     // Wczytanie stosu 2 (od spodu do góry)
  25.     for (int i = 0; i < m; i++) cin >> B[i];
  26.  
  27.     // ODWRACAMY tablice, aby indeks 0 oznaczał górę stosu (pierwszy do zdjęcia)
  28.     reverse(A.begin(), A.end());
  29.     reverse(B.begin(), B.end());
  30.  
  31.     // Tablica DP: dp[i][j] przechowuje wynik dla stanu, gdzie
  32.     // zdjęto 'i' naleśników z lewego stosu i 'j' z prawego.
  33.     // Rozmiar to (n+1) x (m+1)
  34.     vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  35.  
  36.     // Wypełniamy tablicę od końca (od momentu, gdy talerze są puste)
  37.     for (int i = n; i >= 0; i--) {
  38.         for (int j = m; j >= 0; j--) {
  39.  
  40.             // Stan końcowy: oba talerze puste -> suma 0
  41.             if (i == n && j == m) {
  42.                 dp[i][j] = 0;
  43.                 continue;
  44.             }
  45.  
  46.             // Sprawdzamy czyja tura. 
  47.             // Liczba wykonanych ruchów to (i + j).
  48.             // Jeśli parzysta -> Bajtek (zaczyna od 0).
  49.             bool bajtekTurn = ((i + j) % 2 == 0);
  50.  
  51.             if (bajtekTurn) {
  52.                 // Tura Bajtka: Chce ZMAKSYMALIZOWAĆ swoją sumę
  53.                 int opcjaA = -INF, opcjaB = -INF;
  54.  
  55.                 // Jeśli może wziąć ze stosu A
  56.                 if (i < n) opcjaA = A[i] + dp[i + 1][j];
  57.                 // Jeśli może wziąć ze stosu B
  58.                 if (j < m) opcjaB = B[j] + dp[i][j + 1];
  59.  
  60.                 dp[i][j] = max(opcjaA, opcjaB);
  61.             } else {
  62.                 // Tura Bitka: Chce ZMINIMALIZOWAĆ sumę Bajtka
  63.                 // Bitek bierze naleśnik dla siebie, więc do sumy Bajtka dodajemy 0 (tylko przechodzimy do nast. stanu)
  64.                 int opcjaA = INF, opcjaB = INF;
  65.  
  66.                 if (i < n) opcjaA = dp[i + 1][j];
  67.                 if (j < m) opcjaB = dp[i][j + 1];
  68.  
  69.                 dp[i][j] = min(opcjaA, opcjaB);
  70.             }
  71.         }
  72.     }
  73.  
  74.     // Wynik dla stanu początkowego (0 zdjętych naleśników)
  75.     cout << dp[0][0] << endl;
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3 3
2 7 -5
10 -2 -3
stdout
copy 
2
https://ideone.com/uCPmku
language:
C++14 (gcc 8.3)
created:
15 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!