oj.uz

Submission #1065848

# Submission time Handle Problem Language Result Execution time Memory
1065848 2024-08-19T12:18:42 Z Rafi22 Peru (RMI20_peru) C++14
18 / 100
 600 ms 69716 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 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+1,0});
	FOR(i,1,n+1)
	{
		int last=-1;
		while(X.back().st<a[i]) 
		{
			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+1,n+1});
	ROF(i,n,0)
	{
		int last=-1;
		while(X.back().st<=a[i]) 
		{
			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});
		if(i>=k) DP[i]=DP[i-k]+Q[0].st;
		for(auto [j,c]:G[i])
		{
			debug(i,j,c);
			DP[i]=min(DP[i],DP[j]+c);
		}
	}*/
	FOR(i,1,n)
	{
		DP[i]=infl;
		int mx=0;
		ROF(j,i,1)
		{
			if(i-j+1>k) break;
			mx=max(mx,a[j]);
			DP[i]=min(DP[i],DP[j-1]+mx);
		}
	}
	ROF(i,n-1,1) DP[i]=min(DP[i],DP[i+1]);
	FOR(i,1,n) debug(DP[i]);
	ll h=0,pot=1;
	ROF(i,n,1)
	{
		h=(h+DP[i]%mod*pot)%mod;
		pot=pot*23%mod;
	}
    return (int)h;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 59228 KB Output is correct
2 Correct 23 ms 59228 KB Output is correct
3 Correct 23 ms 59248 KB Output is correct
4 Correct 25 ms 59196 KB Output is correct
5 Correct 23 ms 59228 KB Output is correct
6 Correct 23 ms 59208 KB Output is correct
7 Correct 24 ms 59224 KB Output is correct
8 Correct 25 ms 59228 KB Output is correct
9 Correct 24 ms 59076 KB Output is correct
10 Correct 25 ms 59228 KB Output is correct
11 Correct 24 ms 59112 KB Output is correct
12 Correct 25 ms 59228 KB Output is correct
13 Correct 27 ms 59184 KB Output is correct
14 Correct 23 ms 59248 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 59228 KB Output is correct
2 Correct 23 ms 59228 KB Output is correct
3 Correct 23 ms 59248 KB Output is correct
4 Correct 25 ms 59196 KB Output is correct
5 Correct 23 ms 59228 KB Output is correct
6 Correct 23 ms 59208 KB Output is correct
7 Correct 24 ms 59224 KB Output is correct
8 Correct 25 ms 59228 KB Output is correct
9 Correct 24 ms 59076 KB Output is correct
10 Correct 25 ms 59228 KB Output is correct
11 Correct 24 ms 59112 KB Output is correct
12 Correct 25 ms 59228 KB Output is correct
13 Correct 27 ms 59184 KB Output is correct
14 Correct 23 ms 59248 KB Output is correct
15 Correct 494 ms 69428 KB Output is correct
16 Correct 387 ms 69460 KB Output is correct
17 Correct 236 ms 69624 KB Output is correct
18 Correct 264 ms 69716 KB Output is correct
19 Correct 367 ms 69504 KB Output is correct
20 Execution timed out 640 ms 69544 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 69428 KB Output is correct
2 Correct 387 ms 69460 KB Output is correct
3 Correct 236 ms 69624 KB Output is correct
4 Correct 264 ms 69716 KB Output is correct
5 Correct 367 ms 69504 KB Output is correct
6 Execution timed out 640 ms 69544 KB Time limit exceeded
7 Halted 0 ms 0 KB -