Submission #1088766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088766		vjudge1	Discharging (NOI20_discharging)	C++17	100 / 100	126 ms	25716 KiB

Discharging

#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
const int maxn=1e6+33;
const int N=1e5;
const int mod=1e9+7;
const long long INF=1e18+2;
int n,cost[1505][1505],a[maxn];
int dp[maxn];
void sub1()
{
    for(int i=1;i<=n;i++)
    {
        cost[i][i]=a[i];
        for(int j=i+1;j<=n;j++)
        {
            cost[i][j]=max(cost[i][j-1],a[j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=cost[1][i]*n;
        for(int j=1;j<i;j++)
        {
            dp[i]=min(dp[i],dp[j]+cost[j+1][i]*(n-j));
        }
    }
    cout<<dp[n];
}
struct line
{
    int a,b;
};
long double intersect(line x,line y)
{
    return -1.0*(x.b-y.b)/(x.a-y.a);
}
vector<line> cht;
vector<long double> point;
void add(line x)
{
    while(!cht.empty()&&intersect(x,cht.back())<=point.back())
    {
        cht.pop_back();
        point.pop_back();
    }
    point.push_back(intersect(cht.back(),x));
    cht.push_back(x);
}
int get(int x)
{
    int kk=upper_bound(point.begin(),point.end(),x)-point.begin()-1;
    return cht[kk].a*x+cht[kk].b;
}
void sub2()
{
    int Max=0;
    cht.push_back({0,0});
    point.push_back(-INF);
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=Max) a[i]=Max;
        if(a[i]>Max)
        {
            Max=a[i];
        }
        dp[i]=get(a[i])+n*a[i];
        add({-i,dp[i]});
    }
    cout<<dp[n];
}
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n;
    int inc=0,dec=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i>1&&a[i]>a[i-1]) inc=1;
        if(i>1&&a[i]<a[i-1]) dec=1;
    }
    if(n<=1500) sub1();
    else sub2();
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:88:9: warning: variable 'inc' set but not used [-Wunused-but-set-variable]
   88 |     int inc=0,dec=0;
      |         ^~~
Discharging.cpp:88:15: warning: variable 'dec' set but not used [-Wunused-but-set-variable]
   88 |     int inc=0,dec=0;
      |               ^~~
Discharging.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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