QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#477295#323. Hillslitvinas7 0ms3816kbC++142.8kb2024-07-14 01:14:282024-07-14 01:14:29

Judging History

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

  • [2024-07-14 01:14:29]
  • 评测
  • 测评结果:7
  • 用时:0ms
  • 内存:3816kb
  • [2024-07-14 01:14:28]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<pair<int,int>,int>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
//ifstream fin ("sleepy.in");
//ofstream fout ("sleepy.out");
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
const int INF = 10000000000000000;
const int mod = 1000000007;
int32_t main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<vector<vector<int>>> dp(n + 1,vector<vector<int>> (n + 1,vector<int> (2,INF)));
    for (int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    dp[0][0][0] = 0;
    if (n > 1)
        dp[0][1][1] = max((int)0,a[1] - a[0] + 1);
    else
        dp[0][1][1] = 0;
    for (int i = 1;i < n;i++)
    {
        for (int k = 0;k <= i;k++)
        {
            if (k == 0)
            {
                dp[i][k][0] = dp[i - 1][k][0];
                continue;
            }
            dp[i][k][0] = min(dp[i - 1][k][0],dp[i - 1][k][1]);
            if (i < n - 1)
            {
                int next = max(a[i + 1] - a[i] + 1,(int)0);
                dp[i][k][1] = dp[i - 1][k - 1][0] + max(a[i - 1] - a[i] + 1,(int)0) + next;
                if (i >= 2)
                {
                    int prev = max(a[i - 1] - a[i - 2] + 1,(int)0);
                    if (i - 2 > 0)
                        prev = max(prev,max(a[i - 3] - a[i - 2],(int)0));
                    int add = max(max(a[i - 1] - a[i] + 1,(int)0) - prev,(int)0);
                    dp[i][k][1] = min(dp[i][k][1],dp[i - 2][k - 1][1] + add + next);
                }
            }
            else
            {
                
                dp[i][k][1] = dp[i - 1][k - 1][0] + max(a[i - 1] - a[i] + 1,(int)0);
                if (i >= 2)
                {
                    int prev = max(a[i - 1] - a[i - 2] + 1,(int)0);
                    if (i - 2 > 0)
                        prev = max(prev,max(a[i - 3] - a[i - 2],(int)0));
                    int add = max(max(a[i - 1] - a[i] + 1,(int)0) - prev,(int)0);
                    dp[i][k][1] = min(dp[i][k][1],dp[i - 2][k - 1][1] + add);
                }
            }
        }
    }
    int x = n / 2;
    if (n % 2)
        x++;
    for (int k = 1;k <= x;k++)
    {
        cout << min(dp[n - 1][k][0],dp[n - 1][k][1]) << " ";
    }
    cout << '\n';
    return 0;
}

詳細信息

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 0ms
memory: 3580kb

input:

3
1 2 4

output:

0 2 

result:

ok 2 number(s): "0 2"

Test #2:

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

input:

3
3 2 1

output:

0 2 

result:

ok 2 number(s): "0 2"

Test #3:

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

input:

3
1 2 1

output:

0 2 

result:

ok 2 number(s): "0 2"

Test #4:

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

input:

3
3 3 3

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #5:

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

input:

3
50 80 80

output:

1 31 

result:

ok 2 number(s): "1 31"

Test #6:

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

input:

3
80 80 50

output:

1 31 

result:

ok 2 number(s): "1 31"

Test #7:

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

input:

3
1 100 1

output:

0 100 

result:

ok 2 number(s): "0 100"

Test #8:

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

input:

3
100 1 100

output:

0 0 

result:

ok 2 number(s): "0 0"

Test #9:

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

input:

3
100 100 100

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #10:

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

input:

3
1 1 1

output:

1 1 

result:

ok 2 number(s): "1 1"

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #11:

score: 15
Accepted
time: 0ms
memory: 3800kb

input:

1
10

output:

0 

result:

ok 1 number(s): "0"

Test #12:

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

input:

2
1 100

output:

0 

result:

ok 1 number(s): "0"

Test #13:

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

input:

2
2 2

output:

1 

result:

ok 1 number(s): "1"

Test #14:

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

input:

10
2 2 4 4 3 1 1 2 3 2

output:

0 1 2 3 5 

result:

ok 5 number(s): "0 1 2 3 5"

Test #15:

score: -15
Wrong Answer
time: 0ms
memory: 3612kb

input:

10
32 48 20 20 15 2 11 5 10 34

output:

0 0 0 1 30 

result:

wrong answer 5th numbers differ - expected: '31', found: '30'

Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%