Advertisement
erek1e

IOI '96 P1 - A Game

Jun 6th, 2022
653
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     int n; cin >> n;
  8.     vector<int> a(n);
  9.     for (int &x : a) cin >> x;
  10.     vector<vector<int>> score[2];
  11.     score[0] = score[1] = vector<vector<int>>(n, vector<int>(n));
  12.     for (int i = 0; i < n; ++i) score[0][i][i] = a[i];
  13.     for (int sz = 2; sz <= n; ++sz) {
  14.         for (int left = 0; left+sz <= n; ++left) {
  15.             int right = left+sz-1;
  16.             int opt1 = a[left] + score[1][left+1][right];
  17.             int opt2 = a[right] + score[1][left][right-1];
  18.             if (opt1 > opt2) {
  19.                 score[0][left][right] = opt1;
  20.                 score[1][left][right] = score[0][left+1][right];
  21.             } else {
  22.                 score[0][left][right] = opt2;
  23.                 score[1][left][right] = score[0][left][right-1];
  24.             }
  25.         }
  26.     }
  27.     cout << score[0][0][n-1] << ' ' << score[1][0][n-1] << endl;
  28.     return 0;
  29. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement