Submission #1152480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152480		at128	Stove (JOI18_stove)	C++20	0 / 100	2 ms	320 KiB

stove

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>     
#include <ext/pb_ds/tree_policy.hpp>  

using namespace std;
using namespace __gnu_pbds;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef tree<
    int,
    null_type,
    less_equal<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;
typedef tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordered_multiset;    
 
#define all(v)              ((v).begin()), ((v).end())
#define sz(v)               ((int)((v).size()))
#define pb                  push_back
 
typedef long long         ll;



 
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    if(n==1){
        cout<<1<<"\n";
        return;
    }
    if(k==1){
        cout<<v.back()-v[0]+1<<"\n";
        return;
    }
    vector<pair<int,int>>d;
    for(int i=0;i<n-1;i++){
        d.pb({v[i+1]-v[i],-i});
    }
    sort(all(d));
    reverse(all(d));
    vector<int>idx;
    for(int i=0;i<k-1;i++){
        idx.pb(-d[i].second);
    }
    sort(all(idx));
    ll res=0,s=v[0];
    for(int i=0;i<idx.size();i++){
        res+=v[idx[i]]-s+1;
        s=v[idx[i]+1];
    }
    res+=v.back()-s+1;
    cout<<res;
}
 
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
 
    int t=1;
    // cin>>t;
    while(t--) solve();
 
}

Compilation message (stderr)

stove.cpp: In function 'int32_t main()':
stove.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
stove.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50