Submission #1307408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307408		HoriaHaivas	Discharging (NOI20_discharging)	C++20	9 / 100	2 ms	1032 KiB

Discharging

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

pair<int,int> dp[2005];
int v[2005];
const int inf=1e18;

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,mx;
    cin >> n;
    for (i=1;i<=n;i++)
    {
         cin >> v[i];
         dp[i].first=inf;
         dp[i].second=inf;
    }
    dp[0].first=0;
    dp[0].second=0;
    for (i=1;i<=n;i++)
    {
         mx=-1;
         for (j=i;j>=1;j--)
         {
              mx=max(mx,v[j]);
              if (dp[j-1].second+(dp[j-1].first+mx)*(i-j+1)<=dp[i].second)
              {
                  if (dp[j-1].second+(dp[j-1].first+mx)*(i-j+1)<dp[i].second)
                  {
                      dp[i].second=dp[j-1].second+(dp[j-1].first+mx)*(i-j+1);
                      dp[i].first=dp[j-1].first+mx;
                  }
                  else
                  dp[i].first=min(dp[i].first,dp[j-1].first+mx);
              }
         }
    }
    cout << dp[n].second;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28