Submission #1052759

#TimeUsernameProblemLanguageResultExecution timeMemory
1052759whyalwaysmezzzStove (JOI18_stove)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--) #define BIT(mask,i) ((mask >> i) & 1ll ) #define endl '\n' #define all(x) x.begin(),x.end() #define ii pair <int,int> using namespace std; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } else return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } else return false; } template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); } const long long oo = 1e18; const int N = 1e6+5; const int MOD = 1e9+7; int a[N]; int n,k; int check(int x) { int cnt = 0; FOR(i,1,n-1) { if (a[i+1] - a[i] > x) cnt++; } return cnt; } void PhongCach() { cin >> n >> k; FOR(i,1,n) cin >> a[i]; int l = 0; int res = oo; int r = 1e9; while (r - l > 1) { int m = r + l >> 1; if (check(m) < k) { r= m; res = min(res,m); } else l = m; } int ans =1; priority_queue <int> V; FOR(i,1,n-1) { if (a[i+1] - a[i] == 1) {ans+=1;continue;} if (a[i+1] - a[i] > res) ans += 1,k--; else V.push(-a[i+1]+a[i]); } while (k > 1) { k--; V.pop(); ans++; } while (V.size()) ans-=V.top(),V.pop(); cout << ans; return; } #define TASK "task" signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(TASK".inp","r",stdin); //freopen(TASK".out","w",stdout); int Sty1e = 1; // cin >> Sty1e; while (Sty1e--) PhongCach(); return 0; }

Compilation message (stderr)

stove.cpp: In function 'void PhongCach()':
stove.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int m = r + l >> 1;
      |           ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...