Submission #1107047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107047		8pete8	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	244 ms	89276 KiB

constellation3

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=1e18,minf=-1e18,lg=30;
//#undef int
int n,k,m;
void setIO(string name){		
	ios_base::sync_with_stdio(0); cin.tie(0);		
	freopen((name+".in").c_str(),"r",stdin);		
	freopen((name+".out").c_str(),"w",stdout);	
}
int h[mxn+10];
vector<pair<pii,int>>star;
vector<pii>add[mxn+10];
map<int,int>dp[mxn+10],dp2[mxn+10];
int last[mxn+10],sub[mxn+10];
int l[mxn+10],r[mxn+10];
void shift(int cur,int x){
    auto it=dp2[cur].begin();
    while(it!=dp2[cur].end()&&(*it).f<=x){
        if((*it).s-last[cur]>0){
            dp[cur][(*it).f]+=(*it).s-last[cur];
            sub[cur]+=(*it).s-last[cur];
            last[cur]=(*it).s;
        }
        it=dp2[cur].erase(it);
    }
}
pii a={-1,-1},b={-1,-1};
void merge(int p,int c){
    shift(c,h[p]);
    if(dp[p].size()<dp[c].size())swap(dp[p],dp[c]);
    if(dp2[p].size()<dp2[c].size())swap(dp2[p],dp2[c]),swap(sub[p],sub[c]),swap(last[p],last[c]);
    for(auto i:dp[c])dp[p][i.f]+=i.s;
    for(auto i:dp2[c])dp2[p][i.f]=max(dp2[p][i.f],i.s-sub[c]+sub[p]);
}
void dfs(int cur){
    for(auto i:add[cur])dp2[cur][i.f]=i.s;
    if(l[cur])dfs(l[cur]),merge(cur,l[cur]);
    if(r[cur])dfs(r[cur]),merge(cur,r[cur]);
}
int32_t main(){
    fastio
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    cin>>m;
    for(int i=0;i<m;i++){
        int x,y,c;cin>>x>>y>>c;
        ans+=c;
        add[x].pb({y,c});
    }
    stack<int>st;
    int root=0;
    for(int i=1;i<=n;i++){
        if(h[i]>=h[root])root=i;
        while(!st.empty()&&h[st.top()]<=h[i])l[i]=st.top(),st.pop();
        if(!st.empty())r[st.top()]=i;
        st.push(i);
    }
    dfs(root);
    for(auto i:dp[root])ans-=i.s;
    int mx=0;
    for(auto i:dp2[root])mx=max(mx,i.s-sub[root]);
    cout<<ans-mx;
}
/*
7 9 0 8HERE
2 9
_____
3 18
4 22
5 3


5 0 0 0HERE
_____
4 8
5 3
8 17

6 8 5 7HERE
2 9
3 18
4 12
_____
5 3
6 15
8 17
*/

Compilation message (stderr)

constellation3.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
constellation3.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void setIO(string name){
      |                       ^
constellation3.cpp:49:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 | void shift(int cur,int x){
      |                         ^
constellation3.cpp:61:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   61 | void merge(int p,int c){
      |                       ^
constellation3.cpp:68:17: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   68 | void dfs(int cur){
      |                 ^
constellation3.cpp:73:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int32_t main(){
      |              ^
constellation3.cpp: In function 'void setIO(std::string)':
constellation3.cpp:40:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
constellation3.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65