oj.uz

Submission #761271

# Submission time Handle Problem Language Result Execution time Memory
761271 2023-06-19T12:27:28 Z ksu2009en Peru (RMI20_peru) C++17
0 / 100
 1 ms 340 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* b){
    vector<ll>dp(n + 1), a(n + 1);
    for(int i = 0; i < n; i++)
        a[i + 1] = b[i];
        
    dp[1] = a[1];
    
    vector<ll>mx(n + 1);
    mx[1] = a[1];
        
    for(int i = 2; i <= n; i++){
        dp[i] = (dp[i - 1] + (ll)a[i]);
        
        ll last = 1;
        
        for(int j = i - 1; j >= max(0, i - k + 1); j--){
            mx[j] = max(mx[j], (ll)a[i]);
            if(mx[j] > a[i]){
                last = j + 1;
                break;
            }
        }
       
        ll l = max(1, i - k + 1), r = i - 1;
        
        //cout << "  ___ " << i << endl;
        
        while(l < r){
            //cout << l << ' ' << r << endl;
            ll m1 = l + (r - l) / 3;
            ll m2 = r - (r - l) / 3;
            
            ll f1 = dp[m1 - 1] + mx[m1], f2 = dp[m2 - 1] + mx[m2];
            
            //cout << dp[m2 - 1] << ' ' << mx[m2] << endl;
            //cout << m1 << ' ' << m2 << ' ' << f1 << ' ' << f2 << endl;
            
            if(f1 < f2){
                r = m2 - 1;
            }
            else{
                l = m1 + 1;
            }
        }
        
        dp[i] = dp[l - 1] + mx[l];
        mx[i] = a[i];
    }
    
    ll p = 1;
    
    ll ans = 0;
    for(int i = n; i >= 1; i--){
        dp[i] %= mod;
        
        ans = (ans + (p * dp[i]) % mod) % mod;
        
        p = (p * 23) % mod;
    }
    
    
    return ans;
}

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:39:12: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   39 |         ll last = 1;
      |            ^~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -