oj.uz

답안 #1065898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065898 2024-08-19T12:44:04 Z Rafi22 Peru (RMI20_peru) C++14
0 / 100
 25 ms 59224 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;
	int mx=0;
	FOR(i,1,k)
	{
		mx=max(mx,a[i]);
		G[i].pb({0,mx});
	} 
	mx=0;
	ROF(i,n,n-k+1)
	{
		mx=max(mx,a[i]);
		G[n].pb({i-1,mx});
	}
	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,Q1;
	Q1.pb({0,0});
	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();
		while(sz(Q1)>0&&Q1[0].nd<i-k) Q1.pop_front();
		Q.pb({a[i],i});
		if(i>=k) DP[i]=Q1[0].st+Q[0].st;
		for(auto [j,c]:G[i])
		{
			debug(i,j,c);
			DP[i]=min(DP[i],DP[j]+c);
		}
		while(sz(Q1)>0&&Q1.back().st>=DP[i]) Q1.pop_back();
		Q1.pb({DP[i],i});
	}
	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;
}

Compilation message

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

Subtask #1
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 59224 KB Output is correct
2 Correct 25 ms 59220 KB Output is correct
3 Incorrect 23 ms 59224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 59224 KB Output is correct
2 Correct 25 ms 59220 KB Output is correct
3 Incorrect 23 ms 59224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 59224 KB Output is correct
2 Correct 25 ms 59220 KB Output is correct
3 Incorrect 23 ms 59224 KB Output isn't correct
4 Halted 0 ms 0 KB -