oj.uz

Submission #1065952

# Submission time Handle Problem Language Result Execution time Memory
1065952 2024-08-19T13:29:30 Z Rafi22 Peru (RMI20_peru) C++14
49 / 100
 600 ms 170376 KB 
#include "peru.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)
int inf=2000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;

const int N=2500007;

ll DP1[N];

ll DP[N];

int a[N];
vector<pair<int,int>>G[N];

int solve(int n,int k,int* v)
{
	FOR(i,1,n) a[i]=v[i-1];
	a[0]=inf,a[n+1]=inf;
	vector<pair<int,int>>X;
	X.pb({inf,0});
	FOR(i,1,n+1)
	{
		int last=-1;
		while(X.back().st<a[i]) 
		{
			if(last!=-1&&i-1-X.back().nd<=k) G[i-1].pb({X.back().nd,last});
			last=X.back().st;
			X.pop_back();
		}
		if(last!=-1&&i-1-X.back().nd<=k) G[i-1].pb({X.back().nd,last});
		X.pb({a[i],i});
	}
	X.clear();
	X.pb({inf,n+1});
	ROF(i,n,0)
	{
		int last=-1;
		while(X.back().st<a[i]) 
		{
			if(last!=-1&&X.back().nd-1-i<=k) G[X.back().nd-1].pb({i,last});
			last=X.back().st;
			X.pop_back();
		}
		if(last!=-1&&X.back().nd-1-i<=k) G[X.back().nd-1].pb({i,last});
		X.pb({a[i],i});
	}
	deque<pair<ll,int>>Q;
	FOR(i,1,n)
	{
		DP[i]=infl;
		if(sz(Q)>0&&Q[0].nd<=i-k) Q.pop_front();
		while(sz(Q)>0&&Q.back().st<a[i]) Q.pop_back();
		Q.pb({a[i],i});
		DP[i]=DP[max(0,i-k)]+Q[0].st;
		for(auto [j,c]:G[i])
		{
			debug(i,j,c);
			DP[i]=min(DP[i],DP[j]+c);
		}
		ROF(j,i-1,1)
		{
			if(DP[j]<=DP[i]) break;
			DP[j]=DP[i];
		}
	}
	/*FOR(i,1,n)
	{
		DP1[i]=infl;
		int mx=0;
		ROF(j,i,1)
		{
			if(i-j+1>k) break;
			mx=max(mx,a[j]);
			DP1[i]=min(DP1[i],DP1[j-1]+mx);
		}
	}
	
	FOR(i,1,n) debug(DP[i],DP1[i]);*/
	ll h=0,pot=1;
	ROF(i,n,1)
	{
		h=(h+DP[i]%mod*pot)%mod;
		pot=pot*23%mod;
	}
    return (int)h;
}

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:77:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |   for(auto [j,c]:G[i])
      |            ^

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 59228 KB Output is correct
2 Correct 26 ms 59224 KB Output is correct
3 Correct 27 ms 59228 KB Output is correct
4 Correct 30 ms 59268 KB Output is correct
5 Correct 26 ms 59232 KB Output is correct
6 Correct 25 ms 59228 KB Output is correct
7 Correct 27 ms 59220 KB Output is correct
8 Correct 25 ms 59240 KB Output is correct
9 Correct 28 ms 59232 KB Output is correct
10 Correct 25 ms 59228 KB Output is correct
11 Correct 29 ms 59096 KB Output is correct
12 Correct 28 ms 59056 KB Output is correct
13 Correct 25 ms 59100 KB Output is correct
14 Correct 25 ms 59232 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 59228 KB Output is correct
2 Correct 26 ms 59224 KB Output is correct
3 Correct 27 ms 59228 KB Output is correct
4 Correct 30 ms 59268 KB Output is correct
5 Correct 26 ms 59232 KB Output is correct
6 Correct 25 ms 59228 KB Output is correct
7 Correct 27 ms 59220 KB Output is correct
8 Correct 25 ms 59240 KB Output is correct
9 Correct 28 ms 59232 KB Output is correct
10 Correct 25 ms 59228 KB Output is correct
11 Correct 29 ms 59096 KB Output is correct
12 Correct 28 ms 59056 KB Output is correct
13 Correct 25 ms 59100 KB Output is correct
14 Correct 25 ms 59232 KB Output is correct
15 Correct 70 ms 78160 KB Output is correct
16 Correct 59 ms 78164 KB Output is correct
17 Correct 59 ms 75724 KB Output is correct
18 Correct 76 ms 80544 KB Output is correct
19 Correct 78 ms 80612 KB Output is correct
20 Correct 73 ms 80724 KB Output is correct
21 Correct 58 ms 77040 KB Output is correct
22 Correct 76 ms 75984 KB Output is correct
23 Correct 81 ms 76452 KB Output is correct
24 Correct 72 ms 73812 KB Output is correct
25 Correct 74 ms 74152 KB Output is correct
26 Correct 60 ms 77140 KB Output is correct
27 Correct 59 ms 78424 KB Output is correct
28 Correct 60 ms 78420 KB Output is correct
29 Correct 64 ms 78676 KB Output is correct
30 Correct 65 ms 77292 KB Output is correct
31 Correct 60 ms 75860 KB Output is correct
32 Correct 64 ms 78164 KB Output is correct
33 Correct 59 ms 75604 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 78160 KB Output is correct
2 Correct 59 ms 78164 KB Output is correct
3 Correct 59 ms 75724 KB Output is correct
4 Correct 76 ms 80544 KB Output is correct
5 Correct 78 ms 80612 KB Output is correct
6 Correct 73 ms 80724 KB Output is correct
7 Correct 58 ms 77040 KB Output is correct
8 Correct 76 ms 75984 KB Output is correct
9 Correct 81 ms 76452 KB Output is correct
10 Correct 72 ms 73812 KB Output is correct
11 Correct 74 ms 74152 KB Output is correct
12 Correct 60 ms 77140 KB Output is correct
13 Correct 59 ms 78424 KB Output is correct
14 Correct 60 ms 78420 KB Output is correct
15 Correct 64 ms 78676 KB Output is correct
16 Correct 65 ms 77292 KB Output is correct
17 Correct 60 ms 75860 KB Output is correct
18 Correct 64 ms 78164 KB Output is correct
19 Correct 59 ms 75604 KB Output is correct
20 Correct 25 ms 59228 KB Output is correct
21 Correct 26 ms 59224 KB Output is correct
22 Correct 27 ms 59228 KB Output is correct
23 Correct 30 ms 59268 KB Output is correct
24 Correct 26 ms 59232 KB Output is correct
25 Correct 25 ms 59228 KB Output is correct
26 Correct 27 ms 59220 KB Output is correct
27 Correct 25 ms 59240 KB Output is correct
28 Correct 28 ms 59232 KB Output is correct
29 Correct 25 ms 59228 KB Output is correct
30 Correct 29 ms 59096 KB Output is correct
31 Correct 28 ms 59056 KB Output is correct
32 Correct 25 ms 59100 KB Output is correct
33 Correct 25 ms 59232 KB Output is correct
34 Correct 324 ms 162820 KB Output is correct
35 Correct 376 ms 170376 KB Output is correct
36 Correct 350 ms 169420 KB Output is correct
37 Correct 499 ms 162964 KB Output is correct
38 Correct 425 ms 165868 KB Output is correct
39 Correct 582 ms 166856 KB Output is correct
40 Execution timed out 836 ms 157188 KB Time limit exceeded
41 Halted 0 ms 0 KB -