oj.uz

Submission #426352

# Submission time Handle Problem Language Result Execution time Memory
426352 2021-06-13T19:04:17 Z TLP39 Discharging (NOI20_discharging) C++14
20 / 100
 149 ms 17800 KB 
#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);
    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--)
    {
        if(t[i-1]==t[i])continue;
        res=v[poi].second.first*(n+1-i)+v[poi].second.second;
        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

Discharging.cpp: In function 'int main()':
Discharging.cpp:40: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]
   40 |         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:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%lld",&t[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 17728 KB Output is correct
2 Correct 139 ms 17696 KB Output is correct
3 Correct 148 ms 17660 KB Output is correct
4 Correct 140 ms 17700 KB Output is correct
5 Correct 149 ms 17732 KB Output is correct
6 Correct 143 ms 17708 KB Output is correct
7 Correct 138 ms 17744 KB Output is correct
8 Correct 146 ms 17800 KB Output is correct
9 Correct 140 ms 17780 KB Output is correct
10 Correct 143 ms 17732 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Halted 0 ms 0 KB -