oj.uz

답안 #768826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768826 2023-06-28T17:33:40 Z dimashhh Stove (JOI18_stove) C++17
50 / 100
 72 ms 47696 KB 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long ll;

const int N = 1e6 + 123,MOD = 1e9 + 7;

int n,k;
ll a[N],dp[5100][5100],mn[5100];
void test(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    mn[0] = -a[1];
    for(int i = 1;i <= k;i++){
        mn[i] = 2e9;
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= min(i,k);j++){
            dp[i][j] = mn[j - 1] + 1 + a[i];
            //cout << dp[i][j] << ' ';
        }
        for(int j = 1;j <= min(i,k);j++) mn[j] = min(mn[j],dp[i][j] - a[i + 1]);
        
        //cout << '\n';

    }
    cout << dp[n][k];
}
int main(){
    cin.tie(0);ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--){
        test();
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 5 ms 12788 KB Output is correct
11 Correct 7 ms 14836 KB Output is correct
12 Correct 15 ms 32084 KB Output is correct
13 Correct 25 ms 43884 KB Output is correct
14 Correct 23 ms 47692 KB Output is correct
15 Correct 24 ms 47696 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 5 ms 12788 KB Output is correct
11 Correct 7 ms 14836 KB Output is correct
12 Correct 15 ms 32084 KB Output is correct
13 Correct 25 ms 43884 KB Output is correct
14 Correct 23 ms 47692 KB Output is correct
15 Correct 24 ms 47696 KB Output is correct
16 Runtime error 72 ms 47332 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -