2022.07.14 Summer training Individual qualifying （ Nine ）

Post game introspection

nothing

Problem F

Source

Codeforces-844D

Answer key

Think the other way , In fact, it's just merging fruits , Turned into 3 Pile up .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;



int n, T = 1, ans;
priority_queue<int, vector<int>, greater<int> >q;

void ready()
{
    
	cin >> n;
	ffor(i, 1, n) {
    
		int a;
		cin >> a;
		q.push(a);
	}
	if (n % 2 == 0) q.push(0);
	while (q.size() > 1) {
    
		int a = q.top(); q.pop();
		int b = q.top(); q.pop();
		int c = q.top(); q.pop();
		int d = a + b + c;
		ans += d;
		q.push(d);
	}
	cout << ans;
}


void work()
{
    

}

signed main()
{
    
	IOS;
	// cin>>T;
	while (T--) {
    
		ready();
		work();
	}
	return 0;
}

Problem H

Source

Codeforces-722C

Answer key

Think backwards , If you turn the deletion upside down into an addend . Add one number at a time , Look at the farthest place on its left , Where is the farthest way to the right , Then update the sum of this interval , And remember to fill the left and right sides .

Code

// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N=1e5+5;
int T=1;
int n,m;
int a[N];
int sum[N];
int id[N];
int l[N],r[N];
int ans;

void ready()
{
    
    stack<int>q;
    cin>>n;
    ffor(i,1,n) cin>>a[i];
    ffor(i,1,n) cin>>id[i];
    ffor(i,1,n) sum[i]=sum[i-1]+a[i];
    ffor(i,1,n){
    
        r[i]=0;
        l[i]=n+1;
    }
    q.push(0);
    rrep(i,n,1){
    
        int ad=id[i];
        l[ad]=min(ad,l[ad-1]);
        r[ad]=max(ad,r[ad+1]);
        r[l[ad]]=r[ad];
        l[r[ad]]=l[ad];
        ans=max(ans,sum[r[ad]]-sum[l[ad]-1]);
        q.push(ans);
    }
    q.pop();
    while(q.size()){
    
        cout<<q.top()<<'\n';
        q.pop();
    }
}

void work()
{
    

}

signed main()
{
    
	IOS;
    ready();
	//cin>>T;
	while (T--) {
    
		work();
	}
	return 0;
}