oj.uz

Submission #538222

# Submission time Handle Problem Language Result Execution time Memory
538222 2022-03-16T10:37:38 Z AdamGS Peru (RMI20_peru) C++17
18 / 100
 600 ms 12644 KB 
#include "peru.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7, LIM=25e5+7, INF=1e18+7;
ll dp[LIM], tr[4*LIM], N=1;
vector<pair<ll,int>>V;
ll cnt(int l, int r) {
  l+=N; r+=N;
  ll ans=max(tr[l], tr[r]);
  while(l/2!=r/2) {
    if(l%2==0) ans=max(ans, tr[l+1]);
    if(r%2==1) ans=max(ans, tr[r-1]);
    l/=2; r/=2;
  }
  return ans;
}
int solve(int n, int k, int* v){
  while(N<n) N*=2;
  rep(i, n) tr[N+i]=v[i];
  for(int i=N-1; i>=0; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  rep(i, k) {
    dp[i]=cnt(0, i);
    while(V.size() && v[i]>=V.back().st) V.pop_back();
    V.pb({v[i], i});
  }
  for(int i=k; i<n; ++i) {
    while(V.size() && v[i]>=V.back().st) V.pop_back();
    V.pb({v[i], i});
    dp[i]=dp[i-k]+cnt(i-k+1, i);
    for(int j=1; j<V.size(); ++j) {
      if(V[j].nd>i-k) dp[i]=min(dp[i], dp[max(V[j-1].nd, i-k)]+V[j].st);
    }
  }
  ll ans=0;
  rep(i, n) ans=(ans*23+dp[i])%MOD;
  return ans;
}

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j=1; j<V.size(); ++j) {
      |                  ~^~~~~~~~~

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 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 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 340 KB Output is correct
14 Correct 1 ms 340 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 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 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 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 371 ms 12644 KB Output is correct
16 Execution timed out 646 ms 12644 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 12644 KB Output is correct
2 Execution timed out 646 ms 12644 KB Time limit exceeded
3 Halted 0 ms 0 KB -