Submission #1258688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258688		maestro194	Stove (JOI18_stove)	C++20	100 / 100	12 ms	1992 KiB

stove

/*
  Author: CNH_Tourist
  Status: Not submitted
*/

#include <bits/stdc++.h>
#pragma GCC optimization ("O3, unroll-loops")
using namespace std;

#define filename "test"
#define endl '\n'
#define X first
#define Y second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define CBIT __builtin_popcount
#define gcd __gcd

void FileInOut()
{
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

  ifstream *fi = new ifstream (filename".inp");
  ofstream *fo = new ofstream (filename".out");
  if(*fi)
  {
    cin.rdbuf( fi->rdbuf() );
    cout.rdbuf( fo->rdbuf() );
  }
}
// unusual mod : 1000003999
// atan2(y, x): tinh goc tao boi oX va diem co toa do (x, y)

const int N = 100005;

int n, k;
int a[N];
vector<pii> v;

void Solve()
{
  cin >> n >> k;
	for(int i = 1; i <= n; i ++)
    cin >> a[i];
  for(int i = 1; i <= n; i ++) {
    int fi = a[i];
    int se = a[i] + 1;
    if (i > 1 && a[i - 1] + 1 == a[i]) {
      fi = v[v.size() - 1].X;
      v.pop_back();
    }
    v.pb({fi, se});
  }

  // for(pii x : v) {
  //   cout << x.X << " " << x.Y << endl;
  // }

  for(int i = 0; i < v.size() - 1; i ++)
    a[i] = v[i + 1].X - v[i].Y;
  sort(a, a + v.size() - 1);
  long long ans = n;
  for(int i = 0; i < min((int)v.size() - k, (int)v.size() - 1); i ++) {
    ans += a[i];
  }
  cout << ans;
  
}

int32_t main()
{
  using namespace std::chrono;
  auto start = high_resolution_clock::now(); 
  FileInOut(); 
  
  int test = 1;
  // cin >> test;
  while(test--)
    Solve();

  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);
  double t = duration.count() * 1.0 / 1000000;
  // cout << endl << "Runtime: " << t << endl;
}

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