QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#361141#8281. Pangu and Stonespaoxiaomo#WA 2ms12784kbC++201.5kb2024-03-22 20:30:082024-03-22 20:30:08

Judging History

你现在查看的是最新测评结果

  • [2024-03-22 20:30:08]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12784kb
  • [2024-03-22 20:30:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[105][105], dp1[105][105][105];
void solve()
{
    int n, ll, rr;
    cin >> n >> ll >> rr;
    vector<int> v(n + 1), fore(n + 1);
    memset(dp, 0x3f, sizeof(dp));
    memset(dp1, 0x3f, sizeof(dp1));
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i], fore[i] = fore[i - 1] + v[i], dp[i][i] = 0;
    }
    for (int len = 2; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            int nu[101][101];
            memset(nu, 0x3f, sizeof(nu));

            for (int tr = l; tr <= r; tr++)
                nu[tr][1] = min(nu[tr][1], dp[l][tr]);

            for (int tr = l + 1; tr <= r; tr++)
            {
                for (int tl = l; tl < tr; tl++)
                {
                    for (int tim = rr; tim > 1; tim--)
                    {
                        nu[tr][tim] = min(nu[tr][tim], nu[tl][tim - 1] + dp[tl + 1][tr]);
                    }
                }
            }
            // cout << nu[3][3] << endl;
            for (int tim = rr; tim >= ll; tim--)
                dp[l][r] = min(dp[l][r], nu[r][tim]);
            dp[l][r] += fore[r] - fore[l - 1];
            // cout << l << " " << r << " " << dp[l][r] << endl;
        }
    }

    cout << dp[1][n] << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12784kb

input:

3 2 2
1 2 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 12780kb

input:

3 2 3
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 12736kb

input:

4 3 3
1 2 3 4

output:

4557430888798830409

result:

wrong answer 1st numbers differ - expected: '0', found: '4557430888798830409'