Submission #426442

#	Time	Username	Problem	Language	Result	Execution time	Memory
426442		TLP39	Discharging (NOI20_discharging)	C++14	100 / 100	196 ms	17736 KiB

Discharging

#include <stdio.h>
#include <math.h>
#include <utility>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long int ll;
typedef pair<ll,pair<ll,ll>> ppl;

ll n;
ll t[1000010]={};
vector<ppl> v;
int main()
{
    scanf("%lld",&n);
    t[0]=0;
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&t[i]);
        t[i]=max(t[i],t[i-1]);
    }
    v.push_back({n+1,{t[n],0}});
    ll poi=0,a,b;
    ll res;
    for(ll i=n;i>0;i--)
    {
        res=v[poi].second.first*(n+1-i)+v[poi].second.second;
        if(t[i-1]==t[i])
        {
            while(poi!=v.size()-1 && v[poi+1].first>=i-1) poi++;
            continue;
        }
        while(!v.empty() && (v[v.size()-1].second.first-t[i-1])*(n+1-v[v.size()-1].first)>=res-v[v.size()-1].second.second)
        {
            v.pop_back();
        }
        a=(v[v.size()-1].second.first-t[i-1]);
        b=res-v[v.size()-1].second.second;
        v.push_back({n+1-(b+a-1)/a,{t[i-1],res}});
        if(i-1<=v[v.size()-1].first) poi=v.size()-1;
        while(poi!=v.size()-1 && v[poi+1].first>=i-1) poi++;
    }
    printf("%lld",v[v.size()-1].second.second);
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:34:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             while(poi!=v.size()-1 && v[poi+1].first>=i-1) poi++;
      |                   ~~~^~~~~~~~~~~~
Discharging.cpp:45:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         while(poi!=v.size()-1 && v[poi+1].first>=i-1) poi++;
      |               ~~~^~~~~~~~~~~~
Discharging.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Discharging.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%lld",&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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