oj.uz

Submission #761161

# Submission time Handle Problem Language Result Execution time Memory
761161 2023-06-19T09:49:43 Z ksu2009en Peru (RMI20_peru) C++17
18 / 100
 600 ms 9204 KB 
#include "peru.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

ll const mod = (ll)(1e9 + 7);

int solve(int n, int k, int* a){
    vector<ll>dp(n);
    
    dp[0] = a[0];
    
    for(int i = 1; i < n; i++){
        dp[i] = (dp[i - 1] + (ll)a[i]);
        
        ll mx = 0;
        for(int j = i; j >= max(0, i - k + 1); j--){
            mx = max(mx, (ll)a[j]);
            
            dp[i] = min(dp[i], (mx + (j - 1 >= 0 ? dp[j - 1] : 0)));
        }
    }
    
    ll p = 1;
    
    ll ans = 0;
    for(int i = n - 1; i >= 0; i--){
        dp[i] %= mod;
        
        ans = (ans + (p * dp[i]) % mod) % mod;
        
        p = (p * 23) % mod;
    }
    
    
    return ans;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 534 ms 9116 KB Output is correct
16 Correct 413 ms 9168 KB Output is correct
17 Correct 235 ms 9164 KB Output is correct
18 Correct 263 ms 9204 KB Output is correct
19 Correct 338 ms 9100 KB Output is correct
20 Execution timed out 659 ms 9160 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 9116 KB Output is correct
2 Correct 413 ms 9168 KB Output is correct
3 Correct 235 ms 9164 KB Output is correct
4 Correct 263 ms 9204 KB Output is correct
5 Correct 338 ms 9100 KB Output is correct
6 Execution timed out 659 ms 9160 KB Time limit exceeded
7 Halted 0 ms 0 KB -