Submission #879616

#	Time	Username	Problem	Language	Result	Execution time	Memory
879616		andrei_boaca	Meetings (IOI18_meetings)	C++17	0 / 100	31 ms	44884 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll n,q,v[100005],rmq[21][100005],loga[100005];
ll s[5005][5005];
ll getmax(ll l,ll r)
{
    ll lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<l)+1]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R)
{
    n=H.size();
    for(int i=1;i<=n;i++)
    {
        v[i]=H[i-1];
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    for(int i=n;i>=1;i--)
    {
        rmq[0][i]=v[i];
        for(int j=1;j<=20;j++)
        {
            rmq[j][i]=rmq[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=n)
                rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            s[i][j]=s[i][j-1]+getmax(min(i,j),max(i,j));
    }
    vector<ll> sol;
    q=L.size();
    for(int z=0;z<q;z++)
    {
        int l=L[z]+1;
        int r=R[z]+1;
        ll ans=1e18;
        for(int i=l;i<=r;i++)
            ans=min(ans,s[i][r]-s[i][l-1]);
        sol.push_back(ans);
    }
    return sol;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40