oj.uz

답안 #938518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938518 2024-03-05T08:40:28 Z Ice_man Chorus (JOI23_chorus) C++14
40 / 100
 42 ms 64244 KB 
#include <iostream>
#include <chrono>

#define maxn 2005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


int n, k;
string s;

void read()
{
    cin >> n >> k;
    cin >> s;

    n *= 2;
    s = ' ' + s;
}


int pref[2][maxn][maxn];
int pom[maxn];


void math()
{
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'A')
            pom[i] = 1;
        else
            pom[i] = -1;
        pom[i] += pom[i - 1];
    }


    for(int i = 0; i < n / 2 + 1; i++)
        for(int j = 1; j <= n; j++)
        {
            pref[0][i][j] = pref[1][i][j] = max(0 , i - pom[j]);

            if(i == 0)
                continue;

            pref[0][i][j] += pref[0][i - 1][j - 1];
            pref[1][i][j] += pref[1][i - 1][j + 1];
        }
}



int dp[maxn][maxn], a[maxn];
int bra, brb;

int calc(int l, int r)
{
    if((r - l + 1) % 2 == 1)
        return INF;

    int ret = 0;
    int len = r - l + 1;
    int mid = (l + r) / 2;

    ret += pref[0][len / 2][mid];
    ret -= pref[0][0][mid - len / 2];
    ret += pref[1][len / 2 - 1][mid + 1];
    ret /= 2;

    return ret;

    /**int ret = 0;

    for(int i = y + 1; i <= x; i++)
        if(a[i] >= y)
            ret += a[i] - y;

    return ret;*/
}


int dp2[maxn][maxn];

void divide(int ansl, int ansr, int l, int r, int son)
{
    if(l > r)
        return;

    int pos = l + r;
    if((l + r) % 2 == 1)
        pos--;

    ///cout << pos << endl;

    dp2[pos][son] = ansr;
    dp[pos][son] = INF;

    for(int i = min(ansr , pos); i >= ansl; i--)
        if(dp[pos][son] > dp[i - 1][son - 1] + calc(i, pos))
        {
            dp[pos][son] = dp[i - 1][son - 1] + calc(i, pos);
            dp2[pos][son] = i;
        }

    int mid = pos / 2;

    divide(ansl, dp2[pos][son], l, mid - 1, son);
    divide(dp2[pos][son], ansr, mid + 1, r, son);
}

int ans = INF;

void solve()
{
    ans = INF;
    for(int i = 1; i <= n; i++)
        dp[i][0] = INF;

    for(int i = 1; i <= k; i++)
    {
        divide(1, n, 1, n / 2, i);
        ans = min(ans, dp[n][i]);
    }

    cout << ans << endl;
}



/**void calc_dp()
{
    bra = 0;
    brb = 0;

    for(char c : s)
        if(c == 'A')
        {
            bra++;
            a[bra] = brb;
        }
        else
            brb++;

    /**for(int i = 0; i < 2 * n; i++)
        cout << a[i] << " ";
    cout << endl;

    cout << bra << " " << brb << endl;*/

/**for(int i = 0; i <= k; i++)
    for(int j = 0; j <= n; j++)
        dp[i][j] = INF;

dp[0][0] = 0;

for(int i = 1; i <= k; i++)
    for(int j = 1; j <= n; j++)
        for(int _k = 0; _k < j; _k++)
        {
            ///cout << calc(_k , j) << endl;
            dp[i][j] = min(dp[i][j] , dp[i - 1][_k] + calc(_k , j));
        }


cout << dp[k][n] << endl;
}*/




int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    read();
    math();
    solve();


    return 0;
}

Compilation message

chorus.cpp:166:5: warning: "/*" within comment [-Wcomment]
  166 |     /**for(int i = 0; i < 2 * n; i++)
      |

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 13912 KB Output is correct
18 Correct 8 ms 30780 KB Output is correct
19 Correct 12 ms 30556 KB Output is correct
20 Correct 5 ms 30696 KB Output is correct
21 Correct 5 ms 30556 KB Output is correct
22 Correct 17 ms 30776 KB Output is correct
23 Correct 18 ms 30780 KB Output is correct
24 Correct 6 ms 30556 KB Output is correct
25 Correct 18 ms 30772 KB Output is correct
26 Correct 15 ms 30556 KB Output is correct
27 Correct 9 ms 30556 KB Output is correct
28 Correct 9 ms 30556 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 13912 KB Output is correct
18 Correct 8 ms 30780 KB Output is correct
19 Correct 12 ms 30556 KB Output is correct
20 Correct 5 ms 30696 KB Output is correct
21 Correct 5 ms 30556 KB Output is correct
22 Correct 17 ms 30776 KB Output is correct
23 Correct 18 ms 30780 KB Output is correct
24 Correct 6 ms 30556 KB Output is correct
25 Correct 18 ms 30772 KB Output is correct
26 Correct 15 ms 30556 KB Output is correct
27 Correct 9 ms 30556 KB Output is correct
28 Correct 9 ms 30556 KB Output is correct
29 Runtime error 42 ms 64244 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 13912 KB Output is correct
18 Correct 8 ms 30780 KB Output is correct
19 Correct 12 ms 30556 KB Output is correct
20 Correct 5 ms 30696 KB Output is correct
21 Correct 5 ms 30556 KB Output is correct
22 Correct 17 ms 30776 KB Output is correct
23 Correct 18 ms 30780 KB Output is correct
24 Correct 6 ms 30556 KB Output is correct
25 Correct 18 ms 30772 KB Output is correct
26 Correct 15 ms 30556 KB Output is correct
27 Correct 9 ms 30556 KB Output is correct
28 Correct 9 ms 30556 KB Output is correct
29 Runtime error 42 ms 64244 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 13912 KB Output is correct
18 Correct 8 ms 30780 KB Output is correct
19 Correct 12 ms 30556 KB Output is correct
20 Correct 5 ms 30696 KB Output is correct
21 Correct 5 ms 30556 KB Output is correct
22 Correct 17 ms 30776 KB Output is correct
23 Correct 18 ms 30780 KB Output is correct
24 Correct 6 ms 30556 KB Output is correct
25 Correct 18 ms 30772 KB Output is correct
26 Correct 15 ms 30556 KB Output is correct
27 Correct 9 ms 30556 KB Output is correct
28 Correct 9 ms 30556 KB Output is correct
29 Runtime error 42 ms 64244 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -