Submission #522229

#	Time	Username	Problem	Language	Result	Execution time	Memory
522229		blue	Kamenčići (COCI21_kamencici)	C++17	0 / 70	0 ms	204 KiB

Main

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    s = " " + s;

    vector<int> red(1+n);
    for(int i = 1; i <= n; i++) red[i] = (s[i] == 'C');

    int I = 1;
    int J = n;

    int dp[1+n+1][1+n+1];
    /*
        if the stones in play currently are [i, j] and both players have played optimally, what is the number
        of stones 1 has?
    */

    dp[1][n] = 0;

    for(int j = n-1; j >= 1; j--)
    {
        dp[1][j] = dp[1][j+1] + ((j+1) % 2 == n % 2) * red[j+1];
    }

    for(int i = 2; i <= n; i++)
    {
        dp[i][n] = dp[i-1][n] + ((i-1) % 2 == n % 2) * red[i-1];
    }

    for(int d = n-1; d >= 0; d--)
    {
        for(int i = 2; i+d < n; i++)
        {
            int j = i+d;

            if((i+j+1) % 2 == (1+n) % 2) //player 1 moves
            {
                dp[i][j] = min(dp[i][j+1] + red[j+1], dp[i-1][j] + red[i-1]);
            }
            else
            {
                dp[i][j] = max(dp[i][j+1], dp[i-1][j]);
            }
        }
    }


}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:22:9: warning: unused variable 'I' [-Wunused-variable]
   22 |     int I = 1;
      |         ^
Main.cpp:23:9: warning: unused variable 'J' [-Wunused-variable]
   23 |     int J = n;
      |         ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40